Sign in
Skip to solution
hardDSA

How do you find the median from a data stream?

240 views
01

Understand the problem

Explain the two-heaps technique.

heapdesign
02

Attempt it yourself

Sketch your approach before reading the solution — that's what interviews test.

Nudge consolestandby

Stuck? Beam a request up — the console returns a conceptual nudge that guides your logic without spoiling the implementation.

03

Study the solution

Keep a max-heap of the lower half and a min-heap of the upper half, balanced in size. The median is the top of one heap (odd count) or the average of both tops (even). Insert is O(log n); median query is O(1).

Solution ready — 2 min read

Classified // press E to declassify

04

Read the code

Two balanced heaps
Run Playground
import heapq

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

    def add_num(self, num):
        heapq.heappush(self.lo, -num)
        heapq.heappush(self.hi, -heapq.heappop(self.lo))   # move max of lo to hi
        if len(self.hi) > len(self.lo):                    # rebalance
            heapq.heappush(self.lo, -heapq.heappop(self.hi))

    def find_median(self):
        if len(self.lo) > len(self.hi):
            return float(-self.lo[0])
        return (-self.lo[0] + self.hi[0]) / 2.0


# --- demo ---
mf = MedianFinder()
for x in [1, 2, 3]:
    mf.add_num(x)
    print(mf.find_median())   # 1.0, then 1.5, then 2.0
05

Join the discussion

Discussion (0)

Sign in to join the discussion.

No responses yet. Be the first to share what you think.

Transmission complete // awaiting log

KEEP THE
STREAK ALIVE.

Dossier 122 of 127 decoded in the Data Structures & Algorithms track. One more won't hurt.

Back to track