Find Median from Data Stream

LeetCode 295 • Hard • AeroSpace • Anduril • two heaps

Sensor readings arrive online. Maintain running median with a max-heap (low half) + min-heap (high half). addNum O(log n), findMedian O(1).

addO(log n)

medianO(1)

median—

lo (max-heap)

hi (min-heap)

Incoming

op—

lo[]

hi[]

Speed:

Ready

Press Play. Balance two heaps so lo holds the lower half.

Whiteboard

Size:3

Type It

class MedianFinder — addNum(num), findMedian(). Two heaps: max-heap lo + min-heap hi.

═══ MEDIAN FINDER (LC 295) ═══

PATTERN ▸ two heaps · balance sizes

① push to lo (as -num), then move lo→hi

② if hi bigger, move hi→lo

|lo| == |hi| or |lo| == |hi|+1

③ median: lo top, or avg of tops

your implementation

Verify: