Heap/Median from Data StreamHard

This practice workspace is built for desktop. Open it on a larger screen to start solving.

Median from Data Stream

Heap·Hard

Design a data structure that supports the following two operations:

addNum(num) — add integer num to the data structure.
findMedian() — return the median of all elements added so far.

If the total number of elements is even, the median is the average of the two middle values. If odd, the median is the middle value.

Pattern — two heaps: maintain a max-heap lo for the lower half and a min-heap hi for the upper half. After every insertion, rebalance so that |lo.size - hi.size| <= 1 and every element in lo is ≤ every element in hi. The median is then either the top of the larger heap, or the average of both tops when the sizes are equal.

Testing harness — dispatcher convention

Because the test runner invokes a single function, implement MedianFinder and expose it through medianOperations(operations). operations is an array of [methodName, ...args] tuples:

["MedianFinder"] — constructor; push null.
["addNum", num] — add a number; push null.
["findMedian"] — return the current median; push the float result.

Example:

medianOperations([
  ["MedianFinder"],
  ["addNum", 1],
  ["addNum", 2],
  ["findMedian"],   // → 1.5
  ["addNum", 3],
  ["findMedian"],   // → 2.0
])
// returns [null, null, null, 1.5, null, 2.0]

Examples

Input: operations = [["MedianFinder"], ["addNum", 1], ["addNum", 2], ["findMedian"], ["addNum", 3], ["findMedian"]]

Output: [null, null, null, 1.5, null, 2.0]

After adding 1 and 2, the median of [1,2] is 1.5. After adding 3, the median of [1,2,3] is 2.0.

Input: operations = [["MedianFinder"], ["addNum", -1], ["findMedian"], ["addNum", -2], ["findMedian"], ["addNum", -3], ["findMedian"]]

Output: [null, null, -1.0, null, -1.5, null, -2.0]

Works with negative numbers; median updates correctly after each insertion.

Constraints

-10^5 <= num <= 10^5
There will be at least one element before any findMedian call.
At most 5 * 10^4 calls in total will be made to addNum and findMedian.

00:00Preview Mode (Read Only)

Loading editor…

Tests

Preview Mode

This is a read-only preview of DSAMind's AI coaching. Sign up to get custom feedback on your own solution.

Passed32 ms

First attempt — retry to track metric movement here.

Your approach

Pattern:Heap
Time:O(N)
Space:O(1)

Complete approach — pattern and complexity both named.

Coach

What you got right

You correctly matched the sorted input requirement and implemented a linear-time scan using two pointers.

Where it diverged

No divergence detected. The code correctly aligns with the stated approach.

Next attempt: focus on

Try solving related sliding window problems to build familiarity with two-pointer variants.

Signals

No signals fired — clean run, you stayed in flow.