DSA Decoded | Day 26: Median From Data Stream

Photo by Hendrik Cornelissen on Unsplash

“This is a running series of posts, where I solve DSA problems and try to explain them as thoroughly as possible for anyone to understand. Usually I’ll be using JAVA for solving all problems”

The link to this question is provided below

[embed]Find Median From Data Stream - NeetCode Leetcode 295. Find Median From Data Stream The [median](https://en.wikipedia.org/wiki/Median) is the middle value…neetcode.io

Problem Statement:

The **median* is the middle value in a sorted list of integers. For lists of even* length, there is no middle value, so the median is the mean of the two middle values.

For example:

• For arr = [1,2,3], the median is 2.
• For arr = [1,2], the median is (1 + 2) / 2 = 1.5

Implement the MedianFinder class:

• MedianFinder() initializes the MedianFinder object.
• void addNum(int num) adds the integer num from the data stream to the data structure.
• double findMedian() returns the median of all elements so far.

Example 1:

Input:
["MedianFinder", "addNum", "1", "findMedian", "addNum", "3" "findMedian", "addNum", "2", "findMedian"]

Output:
[null, null, 1.0, null, 2.0, null, 2.0]

Explanation:
MedianFinder medianFinder = new MedianFinder();
medianFinder.addNum(1);    // arr = [1]
medianFinder.findMedian(); // return 1.0
medianFinder.addNum(3);    // arr = [1, 3]
medianFinder.findMedian(); // return 2.0
medianFinder.addNum(2);    // arr[1, 2, 3]
medianFinder.findMedian(); // return 2.0

Constraints:

• -100,000 <= num <= 100,000
• findMedian will only be called after adding at least one integer to the data structure.

Intuition:

Since a median is always the middle value of the sorted list, for odd length its the middle one and even length, its the average for the middle two.

Using this logic, we keep the stream always divided in two parts, first contains the sorted first half, and second the other greater half. In such scenario, we need to get the max of first half and minimum of second half. For such a case we can use two heaps, max heap for smaller list and min heap for larger list, which would give use max of smallers and min of larger ones respectively.

A simple workflow is :

1. Keep two heaps, max heap for smaller list, and min heap for larger list.
2. By default add incoming values to smaller half first.
3. If the difference in size of both list is greater than 1, (first heap is allowed to have 1 more item, for handling odd length cases), then in order to balance the division of list items, we move the max of lower heap, to larger heap.
4. Also a case could occur, where the top of first half is larger than top of second half, breaking the sorted order. To fix this simply, swap the heads of two heaps.

Solution:

class MedianFinder {
    private Queue<Integer> minHeap, maxHeap;
    private int size;

    public MedianFinder() {
        this.minHeap = new PriorityQueue<>((a,b) -> b-a);
        this.maxHeap = new PriorityQueue<>((a,b) -> a-b);    
    }

    public void addNum(int num) {
        this.minHeap.add(num);
        if( this.minHeap.size() - this.maxHeap.size() > 1 ){
            this.maxHeap.add( this.minHeap.poll() );
        }
        if( !this.maxHeap.isEmpty() && this.maxHeap.peek() < this.minHeap.peek() ){
            this.minHeap.poll();
            this.minHeap.add( this.maxHeap.poll() );
            this.maxHeap.add(num);
        }
    }

    public double findMedian() {
        if(this.minHeap.size() > this.maxHeap.size())
            return this.minHeap.peek();
        else
            return ((double)this.minHeap.peek() + this.maxHeap.peek()) / 2;
    }
}

Complexity:

Time : O(nlogn) , we use priority queues with self sorting.

Space : O(n) , we use two queues.