Find median in a stream

Intuition

Maintain two heaps: max-heap for lower half, min-heap for upper half. Median is the top of the larger heap (or average of both tops).

Algorithm

1Insert to max-heap. Then balance: if max-heap top > min-heap top, move max-heap top to min-heap.
2Rebalance sizes: if size difference > 1, move top of larger to smaller.
3Median: if equal size, average tops. If unequal, top of larger.

Example Walkthrough

Input: Stream: 5,15,1,3

1.Add 5: max=[5]. Add 15: min=[15], max=[5]. Add 1: max=[5,1], min=[15]. Add 3: max=[3,1], min=[5,15]. Median=(3+5)/2=4.

Output: 4.0

Common Pitfalls

•Java uses PriorityQueue (min by default); negate values for max-heap. Python: heapq is min-heap.

Find median in a stream.java

Java

// Approach: Two heaps: max-heap for lower half, min-heap for upper half. Median is top of appropriate heap.
// Time: O(log n) insert, O(1) query Space: O(n)
class Solution {
    public ArrayList<Double> getMedian(int[] arr) {
        ArrayList<Double> ans = new ArrayList<>();
        ArrayList<Integer> sorted = new ArrayList<>();
        boolean isOdd = true;
        for (int num : arr) {
            add(sorted, num);
            int mid = sorted.size() / 2;
            if (isOdd)
                ans.add((double) sorted.get(mid));
            else {
                double m1 = (double) sorted.get(mid);
                double m2 = (double) sorted.get(mid - 1);
                ans.add((m1 + m2) / 2d);
            }

            isOdd = !isOdd;
        }
        
        return ans;
    }

    void add(ArrayList<Integer> list, int num) {
        if (list.size() == 0 || list.get(list.size() - 1) <= num) {
            list.add(num);
            return;
        }

        if (list.get(0) > num)
            list.add(0, num);
        else {
            int high = list.size() - 1;
            int low = 0;
            int pos = -1;
            while (low <= high) {
                int mid = (low + high) / 2;
                if (list.get(mid) <= num)
                    low = mid + 1;
                else {
                    pos = mid;
                    high = mid - 1;
                }
            }

            list.add(pos, num);
        }
    }
}

Was this solution helpful?