loading

Find Median from Data Stream — Step-by-Step Visualization

hardLeetCode #295Two HeapsHeap (Priority Queue)DesignData Stream

The median is the middle value in an ordered integer list. If the size of the list is even, there is no middle value, and the median is the mean of the two middle values. Implement the `MedianFinder` class: `MedianFinder()` initializes the object. `void addNum(int num)` adds the integer `num` from the data stream to the data structure. `double findMedian()` returns the median of all elements so far.

Algorithm Pattern

Two Heaps (Balance Principle)

Key Idea

We can divide the numbers into two halves: the smaller half (stored in a max-heap) and the larger half (stored in a min-heap). The max-heap gives us the largest element of the small half, and the min-heap gives us the smallest element of the large half. By keeping the heap sizes within 1 of each other, the median will always be either the root of the larger heap (if sizes are unequal) or the average of both roots (if sizes are equal).

Step-by-Step Approach

  1. Initialize `small` (max-heap) and `large` (min-heap).
  2. When adding `num`:
  3. Push `num` to `small`.
  4. To maintain order, pop from `small` and push to `large`.
  5. To maintain balance, if `len(large) > len(small)`, pop from `large` and push to `small`.
  6. Find median:
  7. If `len(small) > len(large)`, return root of `small`.
  8. Else, return average of roots of both heaps.

Common Gotchas

  • JavaScript doesn't have a built-in Heap, so we simulate it.
  • The 'small' heap is a MAX-heap, so we negate values if using a min-heap implementation.

Related Problems

← All problems