Find Median from Data Stream

LeetCode 295 — Find Median from Data Stream

Problem

You are given an array of operations on a running stream of integers. Each operation is one of two types:

• [0, x] — add the integer x to the stream.
• [1] — return the median of all integers currently in the stream.

The median is the middle value in the sorted order of the stream. If the stream has an even number of elements, the median is the average of the two middle values.

Return an array containing the answer to each [1] operation, in order. Each operation must run in O(log n).

Example

operations = [[0, 1],
              [0, 2],
              [0, 3],
              [1],
              [0, 100],
              [0, 500],
              [1]]

solution(operations) = [2.0, 3.0]

Walkthrough:

• After [0, 1], [0, 2], [0, 3] the stream is {1, 2, 3}.
• [1] → median is 2.0.
• After [0, 100], [0, 500] the stream is {1, 2, 3, 100, 500}.
• [1] → median is 3.0.

Solution

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.PriorityQueue;

class Solution {

    public double[] solution(int[][] operations) {
        // Two heaps split the stream into halves. Invariants kept after every add:
        //   1. `lower` holds the smaller half of the stream (max-heap, biggest on top).
        //   2. `upper` holds the larger half of the stream (min-heap, smallest on top).
        //   3. Every element in `lower` is <= every element in `upper`.
        //   4. Sizes are balanced: lower.size() == upper.size()   OR
        //                          lower.size() == upper.size() + 1.
        //      (We always keep the "extra" element in `lower` when the total is odd.)
        PriorityQueue<Integer> lower = new PriorityQueue<>(Collections.reverseOrder());
        PriorityQueue<Integer> upper = new PriorityQueue<>();
        List<Double> medians = new ArrayList<>();

        for (int[] op : operations) {
            if (op[0] == 0) {
                int x = op[1];

                // Step A: push to lower unconditionally, then shuttle its top to upper.
                // This guarantees invariant 3 (every lower element <= every upper element)
                // because the new num is compared against lower's max via the heap pop.
                lower.offer(x);
                upper.offer(lower.poll());

                // Step B: rebalance sizes if upper has grown larger than lower.
                // This restores invariant 4 (lower may exceed upper by at most 1).
                if (upper.size() > lower.size()) {
                    lower.offer(upper.poll());
                }
            } else {
                // Query: report the current median in O(1).
                // Odd total -> lower has one extra element, its top is the median.
                // Even total -> average the two middle elements (tops of each heap).
                if (lower.size() > upper.size()) {
                    medians.add((double) lower.peek());
                } else {
                    medians.add((lower.peek() + upper.peek()) / 2.0);
                }
            }
        }

        double[] result = new double[medians.size()];
        for (int i = 0; i < medians.size(); i++) {
            result[i] = medians.get(i);
        }
        return result;
    }
}