Realtime Middle Value Estimator — Problem Statement & Solution Guide

HeapHardMedian from Stream

TimeO(log n) per insertion, O(1) per median query

SpaceO(n) total for storing all elements in the two heaps

Problem Description

Design a system that maintains a sequence of numbers and calculates the median after each new number is added, ensuring the median is always up-to-date. The system should handle a large volume of numbers efficiently.

DSA Pattern Breakdown

"Realtime Middle Value Estimator"

hard

WHY DOES IT MATTER?

Maintaining a running median is a classic online query problem that appears in finance (real‑time price analysis), telemetry, and monitoring dashboards. The two‑heap pattern provides deterministic logarithmic updates and constant‑time queries, which is essential for systems that cannot afford batch recomputation.

OPTIMIZATION CHALLENGE

The breakthrough is recognizing that only the extreme elements of each half (the largest of the lower half and the smallest of the upper half) influence the median, allowing us to discard the rest of the ordering information and store only those extremes in two heaps.

REAL-WORLD CONNECTION

Think of a live news ticker where you constantly need to know the middle sentiment score. Instead of storing all scores and sorting each time, you keep two buckets: one for scores below the current middle and one for scores above, constantly rebalancing as new scores arrive.

During implementation, always insert into the max‑heap first, then move its top to the min‑heap; this guarantees the max‑heap never holds a value larger than any in the min‑heap and simplifies the rebalancing logic.

COMPLEXITY AT A GLANCE

⏱ Time:O(log n) per insertion, O(1) per median query

💾 Space:O(n) total for storing all elements in the two heaps

Core Theory — Why This Approach?

The median of a dynamic data stream can be maintained efficiently using two complementary priority queues (heaps). One max‑heap stores the lower half of the numbers, guaranteeing O(1) access to the largest element of that half, while a min‑heap stores the upper half, providing O(1) access to the smallest element of the upper half. By keeping the sizes of the two heaps balanced (their size difference never exceeds one), the median is either the top of the max‑heap (for odd total count) or the average of the two tops (for even total count). Naïve solutions that sort the entire list after each insertion incur O(n log n) per update, which quickly becomes prohibitive for large streams because each insertion would require re‑sorting or rebuilding the list. The two‑heap approach reduces each insertion to O(log n) by only adjusting the relevant heap and possibly moving a single element between heaps, while retrieval of the median stays O(1). This paradigm exemplifies the “online” algorithm model where answers are required after each incremental update without reprocessing the whole dataset.

Interview Questions on This Problem

Q1How would you design a data structure to support insert(num) and getMedian() in O(log n) and O(1) time respectively?

Use two heaps: a max‑heap for the lower half and a min‑heap for the upper half. On insertion, push the number into the appropriate heap, rebalance sizes if needed, and move the top element between heaps to maintain order. The median is then the top of the max‑heap (or the average of both tops when sizes are equal).

Q2Why can’t we use a single balanced BST (e.g., TreeSet) to achieve the same performance?

A balanced BST gives O(log n) insertion and O(log n) median retrieval because you need to locate the k‑th element, which requires order‑statistics augmentation or an extra pointer. Maintaining the median in O(1) without extra augmentation is harder, whereas the two‑heap method naturally provides constant‑time median access.

Q3In a distributed system processing a high‑throughput event stream, how would you scale the median estimator while preserving low latency?

Partition the stream by key and run an independent two‑heap estimator per partition; periodically merge partial medians using a hierarchical reduction where each level merges two estimators by re‑balancing their heaps. This keeps per‑node latency O(log n) and limits cross‑node communication.

Examples

Example 1

Input

[1, 2, 3, 4, 5]

Output

Explanation: Step-by-step: with input [1, 2, 3, 4, 5], we first initialize the max heap with the first half of the numbers and the min heap with the second half. Then, we add the next number to the appropriate heap and calculate the median. Finally, we return the median.

Example 2

Input

[1, 3, 5, 7, 9, 2, 4, 6, 8, 10]

Output

Explanation: Step-by-step: with input [1, 3, 5, 7, 9, 2, 4, 6, 8, 10], we first initialize the max heap with the first half of the numbers and the min heap with the second half. Then, we add the next number to the appropriate heap and calculate the median. Finally, we return the median.

Constraints

The input stream can contain any positive or negative integers.
The system should handle a large volume of numbers efficiently.
Memory usage should be optimized.

Optimal Approach & Strategy

Maintain two balanced heaps (max‑heap and min‑heap) to keep lower and upper halves; insert in O(log n) and retrieve median in O(1).

Brute Force Approach

Store all numbers in a list, sort it after each insertion, and pick the middle element(s) to compute the median.

Verified Code Solutions

Language:

JavaScript Solution

Time: O(log n) per insertion, O(1) per median query

class MedianFinder {
    constructor() {
        this.maxHeap = new MaxHeap();
        this.minHeap = new MinHeap();
    }

    addNum(num) {
        if (this.maxHeap.size() === 0 || num < this.maxHeap.peek()) {
            this.minHeap.insert(num);
        } else {
            this.maxHeap.insert(num);
        }

        if (this.maxHeap.size() > this.minHeap.size() + 1) {
            this.minHeap.insert(this.maxHeap.extractMax());
        } else if (this.minHeap.size() > this.maxHeap.size()) {
            this.maxHeap.insert(this.minHeap.extractMin());
        }
    }

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

class MedianFinder {
public:
    MedianFinder() {
        maxHeap = new MaxHeap();
        minHeap = new MinHeap();
    }

    void addNum(int num) {
        if (!maxHeap || num < maxHeap->peek()) {
            minHeap->insert(num);
        } else {
            maxHeap->insert(num);
        }

        if (maxHeap->size() > minHeap->size() + 1) {
            minHeap->insert(maxHeap->extractMax());
        } else if (minHeap->size() > maxHeap->size()) {
            maxHeap->insert(minHeap->extractMin());
        }
    }

    double findMedian() {
        if (maxHeap->size() == minHeap->size()) {
            return (maxHeap->peek() + minHeap->peek()) / 2;
        } else {
            return maxHeap->peek();
        }
    }
};

class MedianFinder {
    private MaxHeap maxHeap;
    private MinHeap minHeap;

    public MedianFinder() {
        maxHeap = new MaxHeap();
        minHeap = new MinHeap();
    }

    public void addNum(int num) {
        if (maxHeap.size() == 0 || num < maxHeap.peek()) {
            minHeap.insert(num);
        } else {
            maxHeap.insert(num);
        }

        if (maxHeap.size() > minHeap.size() + 1) {
            minHeap.insert(maxHeap.extractMax());
        } else if (minHeap.size() > maxHeap.size()) {
            maxHeap.insert(minHeap.extractMin());
        }
    }

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

class MedianFinder:
    def __init__(self):
        self.maxHeap = MaxHeap()
        self.minHeap = MinHeap()

    def addNum(self, num):
        if not self.maxHeap or num < self.maxHeap.peek():
            self.minHeap.insert(num)
        else:
            self.maxHeap.insert(num)

        if self.maxHeap.size() > self.minHeap.size() + 1:
            self.minHeap.insert(self.maxHeap.extractMax())
        elif self.minHeap.size() > self.maxHeap.size():
            self.maxHeap.insert(self.minHeap.extractMin())

    def findMedian(self):
        if self.maxHeap.size() == self.minHeap.size():
            return (self.maxHeap.peek() + self.minHeap.peek()) / 2
        else:
            return self.maxHeap.peek()

class MedianFinder {
    constructor() {
        this.maxHeap = new MaxHeap();
        this.minHeap = new MinHeap();
    }

    addNum(num) {
        if (this.maxHeap.size() === 0 || num < this.maxHeap.peek()) {
            this.minHeap.insert(num);
        } else {
            this.maxHeap.insert(num);
        }

        if (this.maxHeap.size() > this.minHeap.size() + 1) {
            this.minHeap.insert(this.maxHeap.extractMax());
        } else if (this.minHeap.size() > this.maxHeap.size()) {
            this.maxHeap.insert(this.minHeap.extractMin());
        }
    }

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

Solve in Interative Editor

Ready to test your code? Open our built-in compiler, run custom test suites, and see detailed complexity analysis reports instantly.

Realtime Middle Value Estimator Solution

Problem Statement

Input

Output

Input

Output

Constraints

More Heap

Optimized Approach

Brute Force Approach

Step-by-Step Dry Run

Tested Solutions

Realtime Middle Value Estimator — Problem Statement & Solution Guide

Problem Description

DSA Pattern Breakdown

Core Theory — Why This Approach?

Interview Questions on This Problem

Examples

Constraints

Optimal Approach & Strategy

Brute Force Approach

Verified Code Solutions

Solve in Interative Editor