#10HardFrom Research to FAANG · 35% acceptance

Median of a Data Stream

HeapDesignTwo Heaps

Design a structure that ingests numbers one at a time and can report the median of everything seen so far at any moment.

Running statistics over a live stream — you have done this on instrument output. The elegant answer is two heaps.

Examples

Input: add(1); add(2); median(); add(3); median()

Output: 1.5, then 2

Constraints

·-10^5 ≤ each number ≤ 10^5
·At most 5×10^4 operations.

Hints

solution.pyPython 3

import heapq

class MedianFinder:
    def __init__(self):
        self.lo = []  # max-heap (negated)
        self.hi = []  # min-heap

    def add(self, num):
        heapq.heappush(self.lo, -num)
        heapq.heappush(self.hi, -heapq.heappop(self.lo))
        if len(self.hi) > len(self.lo):
            heapq.heappush(self.lo, -heapq.heappop(self.hi))

    def median(self):
        if len(self.lo) > len(self.hi):
            return -self.lo[0]
        return (-self.lo[0] + self.hi[0]) / 2

Test console

// hit Run to execute the sample tests

// Interactive editor preview. Live code execution arrives with your early-access cohort.