Sliding Window Median
On this page
Problem statement
Given an array of numbers and a window size k, return the median of every window of k consecutive numbers as the window slides from left to right. With an even k, the median is the average of the two middle values. Return the medians as floating-point numbers.
The natural next step after Find Median from Data Stream: numbers now also leave. It appears in monitoring ("median latency over the last k requests") and in signal smoothing, where a running median ignores spikes that would wreck a running average. Original problem: LeetCode 480.
Example

Input: nums = [5, 2, 8, 1, 9, 4], k = 3
Output: [5.0, 2.0, 8.0, 4.0]
Input: nums = [5, 2, 8, 1, 9, 4], k = 2
Output: [3.5, 5.0, 4.5, 5.0, 6.5]
Constraints (assumed)
- 1 ≤ k ≤ n ≤ 10⁵; values fit in a 32-bit int (including −2³¹ and 2³¹ − 1).
- Answers within 10⁻⁵ of the true median are accepted.
What this question tests
- Reusing the two-heap median idea and adding deletion, which heaps don't support directly.
- Lazy deletion, or choosing an ordered structure (balanced tree, multiset) that supports both insert and delete.
- Numeric care: averaging two large ints without overflow.
Questions to ask first
- How big are n and k? O(n · k) is fine for small windows, not for k = 10⁵.
- Can values repeat? (Here: yes, which matters when deleting by value.)
- Output type? (Here: floats, even when k is odd.)
- Can values reach the int limits? (Here: yes, so the even-k average must not overflow.)
Try it yourself first
You have the full problem. Sketch your answer, then sign up free to read the complete walkthrough.
- The complete design, flow by flow, with pictures
- Deep dives into the hard parts
- What mid, senior and staff candidates are expected to say
- Full company question lists
Free forever. No card needed.