Calculate median in real-time using JavaScript

Let's assume that a customer is spending money daily and we want to calculate the median of the expenses for the last 5 days.

For the first 4 days, we don't have enough data to compute, so we will begin to calculate the median at day number 5.

5th day:

javascript
let expenses = [10, 20, 30, 50, 30];
                -------------------
                last 5 days expenses

let sorted   = [10, 20, 30, 30, 50];
                ---------+---------
                      median

6th day:

javascript
let expenses = [10, 20, 30, 50, 30, 70];
                    -------------------
                    last 5 days expenses
                            
let sorted   = [20, 30, 30, 50, 70];
                ---------+---------
                      median

7th day:

javascript
let expenses = [10, 20, 30, 50, 30, 70, 80];
                        -------------------
                        last 5 days expenses
                            
let sorted   = [30, 30, 50, 70, 80];
                ---------+---------
                      median

As you can see, there are some patterns as days pass by:

1. Sorted has a constant number of items
2. Median is always at the same position
3. The next item to go away from sorted was the first to entry

Setting initial parameters

Let's define a customer object taking into account the previous conditions. customer.sorted counts the frequency of the expenses, customer.median has the value of the median, and customer.nextItemsToRemove is a FIFO array of expenses.

javascript
let customer = {
    
    sorted: {
        '10': 1,
        '20': 1,
        '30': 2,
        '50': 1
    },
    median: 30,
    nextItemsToRemove: [10, 20, 30, 50, 30]

}

Final algorithm

We need to update customer's properties on the go. Let's assume that we are on the 6th day.

As a new day has passed by:

1. Remove an item
2. Add the new one
3. Recalculate the median

javascript

// 1. Get item to remove
let itemToRemove = customer.nextItemsToRemove[0];

// 1a. Remove it from sorted object
if(customer.sorted[itemToRemove] > 1) customer.sorted[itemToRemove] --;
else                                  delete customer.sorted[itemToRemove];

// 1b. Remove item from nextItemsToRemove
customer.nextItemsToRemove = customer.nextItemsToRemove.slice(1);

// 2. Add new item to object
let newItem = expenses[5];

// 2a. Add it to sorted object
if(customer.sorted[newItem] > 0) customer.sorted[itemToRemove] ++;
else                             customer.sorted[itemToRemove] = 1;

// 2b. Add item to nextItemsToRemove
customer.nextItemsToRemove.push(newItem);

// 3. Recalculate median
customer.median = median(customer.sorted);

Defining median function:

javascript
const median = (object) => {

    // Median will always be in the 3rd position
    let position = 3;
    
    // How many times the customer has spent 10, 20, 30, 50
    let expenses  = Object.keys(object);
    let frequency = Object.values(object);
    
    for(let index = 0, sum = 0; index < expenses.length; index ++){
    
        // We sum the elements in the array
        sum = sum + expenses[index];
        
        // Until we arrive to position 3 
        if(sum >= position){
            customer.median = frequency[index];
            break;
        }
        
    }
    
}

The algorithm is valid for day 7th, 8th, 9th, and so forth.

Please, take into account that this is an oversimplification of the problem to get a general idea on how to calculate a moving median on the go. For example, I have assumed that the number of items to calculate the median was odd, but feel free to rethink the example if the number of items was even.