We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
The problem becomes really nice due to time constraints.
To solve this problem we will use two heaps minHeap and maxHeap. minHeap would contain all the elements greater than median (of previous iteration) and maxHeap would contain elements smaller than or equal to median(of previous iterations). Now insert the element accordingly and if the difference of size of minHeap and maxHep is greater than 1 , then pop the element from the heap of big size and insert into nextHeap
Now 3 cases follow up
1. If minHeap.size()== maxHeap.size()
median=(minHeap.top()+ maxHeap.top())/2;
2.Else If minHeap.size()>maxHeap.size()
median=minHeap.top();
3.Else
median=maxHeap.top();
//for inserting first two elements, insert bigger element in minHeap and smaller in maxHeap.
Hope the solution helps. Ping me if any doubt :)
Find the Running Median
You are viewing a single comment's thread. Return to all comments →
The problem becomes really nice due to time constraints. To solve this problem we will use two heaps minHeap and maxHeap. minHeap would contain all the elements greater than median (of previous iteration) and maxHeap would contain elements smaller than or equal to median(of previous iterations). Now insert the element accordingly and if the difference of size of minHeap and maxHep is greater than 1 , then pop the element from the heap of big size and insert into nextHeap Now 3 cases follow up 1. If minHeap.size()== maxHeap.size() median=(minHeap.top()+ maxHeap.top())/2; 2.Else If minHeap.size()>maxHeap.size() median=minHeap.top(); 3.Else median=maxHeap.top(); //for inserting first two elements, insert bigger element in minHeap and smaller in maxHeap. Hope the solution helps. Ping me if any doubt :)