Median of an Integer Stream

Design a data structure to efficiently calculate the running median of a continuously growing stream of numbers. This tests knowledge of heaps and data structure design under dynamic constraints, a common interview theme.

heapdata structuremedianpriority queuedesign

Problem Statement

Implement a MedianFinder class that supports the following operations: - add_number(num: int): Adds a new integer num to the data structure. - find_median() -> float: Returns the median of all numbers added so far. If the number of elements is even, return the average of the two middle elements.

Example 1

Input: add_number(2), add_number(5), find_median(), add_number(1), find_median()

Output: 3.5, 2.0

Initially, the data structure contains [2]. After adding 5, it contains [2, 5]. The median is (2+5)/2 = 3.5. After adding 1, it contains [1, 2, 5]. The median is 2.

Example 2

Input: add_number(8), add_number(3), find_median(), add_number(7), add_number(10), find_median()

Output: 5.5, 7.5

Initially, the data structure contains [8]. After adding 3, it contains [3, 8]. The median is (3+8)/2 = 5.5. After adding 7 and 10, it contains [3, 7, 8, 10]. The median is (7+8)/2 = 7.5.

Constraints

-1 <= Number of calls to add_number and find_median <= 5 * 10^4
--10^5 <= num <= 10^5
-There will be at least one element in the data structure before calling find_median.
-You may assume there are no duplicate numbers in the input stream.

Brute Force Approach

The brute force approach involves storing all numbers in a list and, upon each find_median call, sorting the list and returning the median. Imagine you're a librarian who has to find the middle book on a shelf every time a new book is added - you'd have to re-sort the entire shelf each time. This is inefficient because sorting takes a long time. The time complexity is dominated by sorting.

TimeO(n log n)

SpaceO(n)

Ready to practice?

Work through this problem with AI coaching and get real-time feedback

Practice This Problem