Running Median

TIP103 Unit 12 Session 2 (Click for link to problem statements)

Running Median

A monitoring service streams sensor values one at a time and must report the median of everything seen so far at any moment.

Implement a class that supports adding a number and querying the current median.

class MedianFinder:
    def __init__(self):
        pass

    def add_num(self, num):
        pass

    def find_median(self):
        pass

Problem Highlights

• 💡 Difficulty: Hard
• ⏰ Time to complete: 30-40 mins
• 🛠️ Topics: Heaps (Priority Queues), Two Heaps Pattern, Data Streams

1: U-nderstand

Understand what the interviewer is asking for by using test cases and questions about the problem.

• Established a set (2-3) of test cases to verify their own solution later.
• Established a set (1-2) of edge cases to verify their solution handles complexities.
• Have fully understood the problem and have no clarifying questions.
• Have you verified any Time/Space Constraints for this problem?

• Q: What is the median when an even number of values has been seen?
  • A: The average of the two middle values in sorted order. With an odd count, it is the single middle value.
• Q: Should find_median() return a float even when the count is odd?
  • A: Yes. The example prints 2.0 after three values, so the median is always reported as a float.
• Q: Can add_num() and find_median() calls be interleaved in any order?
  • A: Yes. Values stream in one at a time, and the current median may be queried at any moment, possibly many times.

HAPPY CASE
Input: add_num(1), add_num(2), find_median(), add_num(3), find_median()
Output: 1.5, then 2.0
Explanation: After [1, 2] the two middle values are 1 and 2, so the median is (1 + 2) / 2 = 1.5. After [1, 2, 3] the middle value is 2, reported as 2.0.

EDGE CASE
Input: add_num(7), find_median()
Output: 7.0
Explanation: With a single value, that value is the median.

Input: add_num(5), add_num(5), add_num(-1), add_num(-3), find_median()
Output: 2.0
Explanation: Duplicates and negative values arriving in decreasing order still sort to [-3, -1, 5, 5], so the median is (-1 + 5) / 2 = 2.0.

2: M-atch

Match what this problem looks like to known categories of problems, e.g. Linked List or Dynamic Programming, and strategies or patterns in those categories.

For Streaming/Data Stream Problems that ask for an order statistic, we can consider the following approaches:

• Two Heaps Pattern: Maintain a max-heap for the lower half of the values and a min-heap for the upper half. The median is always available from the heap tops.
• Sorted List with Binary Insertion: Keep all values sorted and insert each new value in place; simpler to reason about, but each insertion costs O(N) for the shift.
• Re-sorting on every query: Works, but sorting the entire stream each time is far too slow for repeated queries.

3: P-lan

Plan the solution with appropriate visualizations and pseudocode.

General Idea: Split the values seen so far into two halves. A max-heap small holds the lower half, and a min-heap large holds the upper half. Keep them balanced so that small has either the same number of elements as large or exactly one more. Then the median is either the top of small (odd count) or the average of the two tops (even count). Python's heapq is a min-heap, so small stores negated values to simulate a max-heap.

1) Initialize two empty heaps: `small` (max-heap via negation) and `large` (min-heap).
2) add_num(num):
   a) Push `num` onto `small`.
   b) Pop the largest value from `small` and push it onto `large`. This guarantees every value in `small` <= every value in `large`.
   c) If `large` now has more elements than `small`, move the smallest value of `large` back to `small`.
3) find_median():
   a) If `small` has more elements, return the top of `small` as a float.
   b) Otherwise, return the average of the top of `small` and the top of `large`.

⚠️ Common Mistakes

• Forgetting to negate values when pushing to or popping from the max-heap, corrupting the ordering.
• Pushing directly onto whichever heap is smaller without routing through the other heap first, which can leave a lower-half value stranded above an upper-half value.
• Letting the heap sizes drift more than one apart, so the heap tops no longer straddle the median.
• Returning an integer for odd counts instead of a float (the expected output is 2.0, not 2).

4: I-mplement

Implement the code to solve the algorithm.

import heapq

class MedianFinder:
    def __init__(self):
        self.small = []  # max-heap via negation: lower half of the numbers
        self.large = []  # min-heap: upper half of the numbers

    def add_num(self, num):
        # Push onto the lower half, then move its largest value to the upper half
        heapq.heappush(self.small, -num)
        heapq.heappush(self.large, -heapq.heappop(self.small))
        # Rebalance so small always holds the extra element on odd counts
        if len(self.large) > len(self.small):
            heapq.heappush(self.small, -heapq.heappop(self.large))

    def find_median(self):
        if len(self.small) > len(self.large):
            return float(-self.small[0])
        return (-self.small[0] + self.large[0]) / 2

5: R-eview

Review the code by running specific example(s) and recording values (watchlist) of your code's variables along the way.

• Input: add_num(1), add_num(2), find_median(), add_num(3), find_median()

  • add_num(1): 1 passes through large and is rebalanced back, so small = {1}, large = {}.
  • add_num(2): 2 is the current max of small, so it moves to large: small = {1}, large = {2}.
  • find_median(): even count, average of tops = (1 + 2) / 2 = 1.5 ✓
  • add_num(3): 3 moves to large, then large is one too big, so 2 moves back: small = {1, 2}, large = {3}.
  • find_median(): odd count, top of small = 2.0 ✓

• Input: add_num(7), find_median()

  • small = {7}, large = {}; odd count, so the median is 7.0 ✓

6: E-valuate

Evaluate the performance of your algorithm and state any strong/weak or future potential work.

Assume N is the number of values added to the stream so far.

• Time Complexity: O(log N) per add_num call, since each of the constant number of heap pushes/pops costs O(log N). find_median is O(1) because it only peeks at the heap tops.
• Space Complexity: O(N) to store every value across the two heaps.