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:

- Sorted has a constant number of items
- Median is always at the same position
- The next item to go away from
`sorted`

was the first to entry

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] }`

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:

- Remove an item
- Add the new one
- 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.

Hi, I'm Erik, an engineer from Barcelona. If you like the post or have any comments, say hi.