Data Structures: Solve 'Find the Running Median' Using Heaps

Learn how to solve 'Finding the Running Median' using heaps. This video is a part of HackerRank's Cracking The Coding Interview Tutorial with Gayle Laakmann McDowell.

[paraschawla]

A hard problem explained so eloquently... Thanks Gayle

[jameswg]

I can't believe I just had this question on my Algorithms course's midterm

[dwstyagi]

I think there is a mistake in a animation video @ 1:16 where you were adding element 10 is at the lower (MaxHeap) heap, but you should be adding it to the upper half. according to the addNumber() explained in the video

[shahzadhassan]

On running the code in video
if input array[] = {1, 2, 3}
median[] = {1.0, 1.5, 3.0}
shouldn't the median[2] = 2.0 ??

[satheshbm]

Loved the explanation, so crisp and concise :)

[kkaabbccdd]

I was asked this question 2 days ago in face-to-face interview in one of the tech giant company in Silicon Valley

[vidhikumar]

First 2 minutes of explanation was exceptional

[vishnuvardhan]

While rebalancing we can check for equal to 2 as there is no chance of greater than 2

[bobesfanchi]

Great explanation Gayle. Thanks for the video.

[youtubeuseran]

These videos are very hepful. Thank you Gayle and Hackerrank! :D

[KaranDoshicool]

Heres the C++ code which I solved after taking hint from the video..considering 4 cases
1)Odd length of array and number inserted less than median
1)Odd length of array and number inserted greater than median
1)Even length of array and number inserted less than median
1)Even length of array and number inserted greater than median
class MedianFinder {
public:
/** initialize your data structure here. */
double median;
int length=0;
priority_queue <int> a;
priority_queue <int, vector<int>, greater<int> > b;
MedianFinder() {

}

void addNum(int num) {
if(a.empty() && b.empty())
{
median=num;
a.push(median);
b.push(median);
length++;
return;

}
else if(num<=median)
{
if(length&1)
{
a.pop();
a.push(num);

}
else
{
a.push(num);
b.push(a.top());

}
}
else if(num>median)
{
if(length&1)
{
b.pop();
b.push(num);
}
else
{
b.push(num);
a.push(b.top());

}
}
length++;





}

double findMedian() {

return median;


}
};
Ping me in case of any doubt :)

[piotrstuglik]

Isn't this a cumulative moving median? You're not removing the oldest items from the original sequence used to create the initial median.

[anantv]

Suppose inputs are 3, 4, 5, 8 : Then min heap will contain 3, max heap contain 5, 4, after then 8 will be also added to max heap, and we will rebalance, final min heap : 3, 8 and max heap 5, 4. Now if we calculate median, it will be 3 + 5/2, which is wrong. I am not getting how above solution is correct.

[gamingparlour]

In c++ it is giving timeout when I used this concept of priority_queue

[chigozie]

No need to cast to double, just write 2.0

[wrushu]

Bigger and Smaller Heap made simplified the approach, can you post the explanation of Sliding Window Median

[pranavganorkar]

While rebalancing the heap, shouldn't the condition be simply (biggerHeap.size() - smallerHeap.size() == 2) instead of (biggerHeap.size() - smallerHeap.size() >= 2) ?

[ramiraguilos]

I had a coding interview recently where I had to find the median in a given array, but then the interviewer brought up the 'running' median as an extension to the problem. I talked about how you could just iterate the brute force solution for O(n^2), but that would be kind of inefficient. I forgot that heaps had the 'min' or 'max' innate characteristic...though, I was skirting around the idea of using a tree based structure to keep track of the median. I thought maybe that a binary search tree or avl tree could be used, but then the interviewer gave me a hint to maybe use heaps instead. Unfortunately, I didn't realize that I was supposed to explain that two heaps could work together to find the median -- so I kind of just made a dumb assumption and said that the median may exist around half the height of the heap? That maybe the numbers around the middle of the heap were the median... After that I was asked to do palindrome checking, which was pretty easy. Though, I had to figure out how to recursively do it on the spot which was pretty simple.

[adityachoudhary]

Great explanation, keep making more videos

[rawanfouda]

Hi! I'm trying to understand the code but I'm confused. what is priorityQueue and what do you mean by forming heaps? Is it that I make two arrays one with the lower half and one with the upper half? what background knowledge do I need to get this?