Find Median from Data Stream | Two Heap | Coding Interview

In this lesson, we will see how to find the median from the data stream. The problem statement is Median is the middle value in an ordered integer list. If the size of the list is even, there is no middle value. So the median is the mean of the two middle values.

Design a data structure that supports the following two operations:

void addNum(int num) - Add an integer number from the data stream to the data structure.
double findMedian() - Return the median of all elements so far.
LeetCode link -

#Heap #coding_interview #Median

To prepare for the interview:
-----------------------------------
Complete list of questions and answers for cracking the coding interview:

[LOKeshrangineni]

Looks like the author forgot to add the heap data structure explanation in the description. If in case someone looking for it

[Legendary-Akshit]

The best and most lucid explanation ever. Thank you for making it so simple to understand.

[vetiarvind]

Are you from Kerela? Your accent seems familiar. You are just answering the problem without going behind the intuition (i.e every element in the min-heap is greater or equal to the median and every element in the max-heap is less or equal to the median. This allows us to take the candidate elements for median calculation in O(1)) I feel like that's the problem with most educators in our country - just go by the answer without going through the "why and what"

[dianayao]

add/remove num into a heap, is time complexity O(log n ), finding is o(1) ?

[mrunaldave]

Just shows the algorithm and does a dry run. Doesn't explain why to do what he is doing.

[swagatpatra]

class MedianFinder {
// define max heap explicitly
PriorityQueue<Integer> max = new PriorityQueue<>((x, y)->y-x);
PriorityQueue<Integer> min = new PriorityQueue<>();

public MedianFinder() {}

public void addNum(int num) {
max.add(num);
min.add(max.remove());
if(max.size()<min.size()) max.add(min.remove());
}

public double findMedian() {
if(max.size() == min.size()) return
return max.peek();
}
}