💬 Discord
Sign In
NeetCode #549LC-295HardHeap / Priority QueueBlind 75NC 150NC 250
← Back to All Problems

#549 · #295 · Find Median from Data Stream(数据流的中位数)

📌 Problem Statement & Constraints

Design a data structure supporting addNum(num) and findMedian(). Constraints: -10^5 <= num <= 10^5; at most 5 * 10^4 calls.

💡 Core Algorithmic Approaches

  1. Keep the lower half in a max-heap and the upper half in a min-heap.
  2. Maintain the invariant that the lower half is the same size as the upper half or exactly one larger.
  3. After each insertion, rebalance by moving one element across if the sizes differ by more than one.
  4. The median is the top of the larger heap (odd count) or the average of the two tops (even count).

💻 Benchmark Python3 Implementation

class MedianFinder:
    def __init__(self):
        self.small = []                    # max-heap (negated) for the lower half
        self.large = []                    # min-heap for the upper half

    def addNum(self, num: int) -> None:
        import heapq
        heapq.heappush(self.small, -num)
        # the largest of the lower half must not exceed the smallest of the upper
        heapq.heappush(self.large, -heapq.heappop(self.small))
        # keep the lower half at least as large as the upper half
        if len(self.large) > len(self.small):
            heapq.heappush(self.small, -heapq.heappop(self.large))

    def findMedian(self) -> float:
        if len(self.small) > len(self.large):
            return -self.small[0]          # odd count -> the middle element
        return (-self.small[0] + self.large[0]) / 2   # even count -> the average

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(log n) per insertion, O(1) per query.
💾 Space Complexity
O(n) for the two heaps.

⚠️ Interview Pitfalls & Follow-ups

  • Keeping a sorted list: insertion is O(n) due to shifting.
  • Skipping the rebalancing step: the median would be wrong once the halves drift apart.
  • Using a single heap: the median is not at either end of a single heap.
  • Returning an integer for the even case: the average may be a half-integer, so a float is required.