Find the Running Median

  • + 13 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 :)