Core Insight Keep only candidates that may become the next answer, ordered by the priority that matters.
Common Pitfall Push only meaningful candidates and remove stale entries before trusting the root.
Description
Design a data structure to find the median from a data stream.
Constraints
- Time Complexity:
O(log n) - Space Complexity:
O(n)
Tags
two-pointersdesignsortingheapdata-stream
Implementation Plan Translate the invariant into these small, testable moves.
- Choose the priority key.
- Push initial candidates.
- Pop the best valid candidate.
- Add newly eligible candidates and repeat.
class MedianFinder:
def __init__(self):
self.small = []
self.large = []
def addNum(self, num: int) -> None:
if self.large and num > self.large[0]:
heapq.heappush(self.large, num)
else:
heapq.heappush(self.small, -1 * num)
if len(self.small) > len(self.large) + 1:
val = -1 * heapq.heappop(self.small)
heapq.heappush(self.large, val)
if len(self.large) > len(self.small) + 1:
val = heapq.heappop(self.large)
heapq.heappush(self.small, -1 * val)
def findMedian(self) -> float:
if len(self.small) > len(self.large):
return -1 * self.small[0]
if len(self.large) > len(self.small):
return self.large[0]
return (-1 * self.small[0] + self.large[0]) / 2