CODEWITHSUNDEEP
algorithmmedian
articuno
articuno

Reputation: 1

Updating the median when removing an element from a list

You are given a list of mixed integers from 1 to n (with no duplicates) say 4,2,6,1,5,3 and the sorted list 1,2,3,4,5,6.

Now the median is 3.5. This is can be calculated in O(1) time when looking at the sorted list 1,2,3,4,5,6. Now remove 4 from the mixed list. Is there an algorithm to update the median in O(1) time? I thought of removing index 4-1=3 from the sorted list and finding the median of that.

This works for the first iteration but not the rest ie when you remove 2, 6 and so on. What I'm wondering if there exists an algorithm for updating the median given that you know:

Upvotes: 0

Views: 1200

Answers (1)

SashaMN
SashaMN

Reputation: 708

I know 2 ways how efficiently solve this problem.

First algorithm:

  1. Use https://en.wikipedia.org/wiki/Order_statistic_tree

You can modify this tree (insert or delete elements) in O(logN) time.

Just perform Select(size / 2) operation to find the median. This is O(logN) solution.

  1. Maintain two binary heaps: https://en.wikipedia.org/wiki/Binary_heap

First heap will contain first size / 2 smallest elements, and keep the maximum in the root.

Second heap will contain last size / 2 biggest elements, and keep the minimum in the root.

Now you can find the median as the root element in the first or in the second heap.

To perform delete (or insert) operation, you can delete the element from the first or second heap (depends on element).

Now, if size(first heap) == size(second heap) + 2, you can remove the maximum from the first heap, and insert to second heap.

If size(first heap) + 2 == size(second heap), you can remove the minimum from the second heap and insert it to first heap.

All this operations take O(logN) time.

Upvotes: 2

Related Questions