Find Median from Data Stream

Problem Context

Imagine you are processing a continuous stream of integers (e.g., real-time sensor readings, live stock prices). At any point in time, you need to be able to report the median of all integers seen so far — efficiently.

The median is the middle value in a sorted list of numbers. If the list has an even number of elements, the median is the average of the two middle values.

Task

Design a data structure that supports the following two operations:

• addNum(num) — Add an integer from the data stream to your data structure.
• findMedian() — Return the median of all elements inserted so far.

You will be given a list of operations and their arguments. Simulate them in order and collect the results of all findMedian calls.

Input / Output Format

Input:

• operations: a list of strings, each either "addNum" or "findMedian"
• values: a list of lists; for addNum, the inner list contains one integer; for findMedian, the inner list is empty

Output:

• A list of results corresponding only to findMedian calls. Each result is a float rounded to 1 decimal place.

Examples

Example 1

operations = ["addNum", "addNum", "findMedian", "addNum", "findMedian"]
values     = [[1], [2], [], [3], []]
Output: [1.5, 2.0]

Explanation:

• Add 1 → stream: [1]
• Add 2 → stream: [1, 2]
• findMedian → sorted: [1, 2] → median = (1+2)/2 = 1.5
• Add 3 → stream: [1, 2, 3]
• findMedian → sorted: [1, 2, 3] → median = 2.0

Example 2

operations = ["addNum", "findMedian"]
values     = [[42], []]
Output: [42.0]

Explanation: Only one element; median is that element itself.

Example 3

operations = ["addNum", "addNum", "addNum", "addNum", "findMedian"]
values     = [[5], [3], [8], [1], []]
Output: [4.0]

Explanation: Sorted: [1, 3, 5, 8] → median = (3+5)/2 = 4.0

Approach Hints

• A naive approach of sorting the entire list on every findMedian call works but is O(n log n) per query — too slow for large streams.
• Think about maintaining two heaps:
  • A max-heap for the lower half of numbers.
  • A min-heap for the upper half of numbers.