Window Medians
Problem
A trading desk smooths a price series nums with a moving median: for every window of k consecutive prices, from nums[0..k-1] to nums[n-k..n-1], it reports the median of that window.
The median of an odd count is the middle value after sorting; of an even count, the average of the two middle values. Return the list of medians as floating-point numbers.
Example 1
- Input:
- nums = [1, 3, -1, -3, 5, 3, 6, 7], k = 3
- Output:
- [1.0, -1.0, -1.0, 3.0, 5.0, 6.0]
Windows: [1,3,-1] → 1, [3,-1,-3] → -1, [-1,-3,5] → -1, [-3,5,3] → 3, [5,3,6] → 5, [3,6,7] → 6.
Example 2
- Input:
- nums = [4, 2, 9, 7], k = 2
- Output:
- [3.0, 5.5, 8.0]
Constraints
- 1 ≤ k ≤ nums.length ≤ 10^5
- -2^31 ≤ nums[i] ≤ 2^31 - 1
Hint
Show the first hint
For a growing collection, a max-heap for the lower half and a min-heap for the upper half give the median. What breaks when values also leave?
Walkthrough
How to approach it
01Clarify before coding
- Return type? Floats, with .5 for even windows.
- Can values be as large as 2^31? Yes; summing two of them for the average is fine in Python and in JavaScript doubles.
- Are there duplicates? Possibly, so deletion must be by count, not by identity.
02Brute force
Sort every window independently and read its middle; or keep a sorted window and insert/delete with binary search plus array shifting.
Cost: Sorting each window is O(n · k log k); the sorted-array version is O(n · k) because of shifting: 10^10 when k is around n/2.
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.