295. Find Median from Data Stream (Hard)

https://leetcode.com/problems/find-median-from-data-stream/

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 value.

[2,3,4], the median is 3

[2,3], the median is (2 + 3) / 2 = 2.5

Design a data structure that supports the following two operations:

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

Example:

addNum(1)
addNum(2)
findMedian() -> 1.5
addNum(3) 
findMedian() -> 2

Follow up:

1. If all integer numbers from the stream are between 0 and 100, how would you optimize it?
2. If 99% of all integer numbers from the stream are between 0 and 100, how would you optimize it?

Solutions

class MedianFinder {

    // This problem is easy and the straight forward way is to employ two PriorityQueue of which one
    // named minQueue is used to keep the smaller values in descending order and the other one named
    // maxQueue serves to keep the larger values than minQueue in ascending order.

    // The reason for adopting two queues is that easy to index since priority queue is not easy to
    // visit the middle element directly. However, we can also use a LinkedList as the container to
    // keep the stream data. It's pretty much like insert sorting when add new elements.

    Queue<Integer> smallerSet = new PriorityQueue<>(Comparator.reverseOrder());
    Queue<Integer> largerSet = new PriorityQueue<>();

    /**
        * initialize your data structure here.
        */
    public MedianFinder() {

    }

    public void addNum(int num) {
        if (smallerSet.size() == 0) {
            smallerSet.add(num);

            return;
        }

        if (num > smallerSet.peek()) {
            largerSet.add(num);
        } else {
            smallerSet.add(num);
        }

        // make sure 0 <= smallerSet.size - largerSet.size < 1

        while (smallerSet.size() - largerSet.size() < 0) {
            smallerSet.add(largerSet.poll());
        }

        while (smallerSet.size() - largerSet.size() > 1) {
            largerSet.add(smallerSet.poll());
        }
    }

    public double findMedian() {
        if ((smallerSet.size() + largerSet.size()) % 2 == 0) {
            return (smallerSet.peek() + largerSet.peek()) / 2.0;
        }

        return smallerSet.peek();
    }
}

Incorrect Solutions

References