Median Board
Problem
A live dashboard tracks the median of a growing collection of response times. It receives a list of operations: ops[i] is either "add", which records the integer vals[i], or "median", which asks for the median of everything recorded so far (vals[i] is 0 and ignored).
The median of an odd count is the middle value after sorting; of an even count it is the average of the two middle values. Return the answers to the "median" operations, in order, as floating-point numbers.
Example 1
- Input:
- ops = ["add", "add", "median", "add", "median"], vals = [5, 1, 0, 9, 0]
- Output:
- [3.0, 5.0]
After 5 and 1 the median is (1 + 5) / 2 = 3. After adding 9 the sorted values are 1, 5, 9 → 5.
Example 2
- Input:
- ops = ["add", "median", "add", "median"], vals = [-4, 0, -7, 0]
- Output:
- [-4.0, -5.5]
Constraints
- 1 ≤ ops.length ≤ 10^5, ops.length == vals.length
- ops[i] is "add" or "median"
- -10^5 ≤ vals[i] ≤ 10^5
- Every "median" comes after at least one "add".
Hint
Show the first hint
The median only depends on the one or two values in the middle. Can you keep the lower half and the upper half apart?
Walkthrough
How to approach it
01Clarify before coding
- Is this a class in disguise? Yes: addNum and findMedian. We model it as parallel lists of operations and values.
- What is returned for an even count? The average of the two middle values, as a float.
- Can a median be asked before any add? No.
02Brute force
Keep all values in a list; on each median query sort it (or keep it sorted with insertion) and read the middle.
Cost: Sorting per query is O(q · n log n); insertion into a sorted array is O(n) per add because of shifting, so O(n²) overall: 10^10 for 10^5 operations.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.
This problem is part of Pro.