hard

Sliding Window Median

Find the median of every fixed-size window as it slides across an array.

1. Define the problem

Sliding Window Median

Given an array nums and a window size k , return the median of each window as it slides from left to right, one value per window position. Copy the window, sort the copy, and read off the middle value — or the average of the two middle values when k is even.

Constraints

  • 1 ≤ k ≤ nums.length ≤ 105
  • -231 ≤ numsi ≤ 231 - 1

Example

Inputnums = [1,3,-1,-3,5,3,6,7], k = 3
Output[1,-1,-1,3,5,6]

Explanation Each position sorts its 3-element window and takes the middle value: [-1,1,3]→1, [-3,-1,3]→-1, [-3,-1,5]→-1, [-3,3,5]→3, [3,5,6]→5, [3,6,7]→6.

2. Know the words first

In plain terms

Median
The middle value of a sorted list — half the values are less than or equal to it and half are greater. For an even-sized list it's the average of the two middle values, e.g. the median of [1,2,3,4] is (2+3)/2 = 2.5.
3. Visualize the solution

Sort each window to find its middle

Sort each window to find its middle
StatusSorted

Window [1,3,-1] sorts to [-1,1,3]; middle value is 1.

What happens in this step

window = [0,2] = [1, 3, -1]
sorted  = [-1, 1, 3]
k=3 is odd → mid index = floor(3/2) = 1 → median = sorted[1] = 1
Step 1 of 6

Steps to visualize

  1. Slide a fixed window of size k from left to right across the array.
  2. Copy the k elements of the window and sort the copy.
  3. If k is odd, the median is the single middle element of the sorted copy.
  4. If k is even, the median is the average of the two middle elements.
  5. Record the median for this position and move the window one step right.
  6. This resorts on every step for teaching clarity — the O(log k)-per-step production answer keeps two balanced heaps instead of resorting.
4. Walk through the code

Walk through the code

Same walkthrough, now with the code. Press Next to move one step and watch which lines run.

Sort each window to find its middle
StatusSorted

Window [1,3,-1] sorts to [-1,1,3]; middle value is 1.

What happens in this step

window = [0,2] = [1, 3, -1]
sorted  = [-1, 1, 3]
k=3 is odd → mid index = floor(3/2) = 1 → median = sorted[1] = 1
Step 1 of 6
5. Solution

Solution

solution.tsTypeScript
function medianSlidingWindow(nums, k) {
  const result = [];

  for (let i = 0; i + k <= nums.length; i++) {
    const window = nums.slice(i, i + k).sort((a, b) => a - b);
    const mid = Math.floor(k / 2);

    if (k % 2 === 1) {
      result.push(window[mid]);
    } else {
      result.push((window[mid - 1] + window[mid]) / 2);
    }
  }

  return result;
}
Time
O(n * k log k)
Space
O(k)
6. Test cases

Test cases

InputExpectedCovers
nums = [1,3,-1,-3,5,3,6,7], k = 3[1,-1,-1,3,5,6]Docstring example
nums = [5,2,8,1], k = 1[5,2,8,1]k = 1 returns each element as its own median
nums = [3,1,2], k = 3[2]k equals array length
nums = [1,2,3,4], k = 2[1.5,2.5,3.5]Even k produces fractional medians
nums = [5], k = 1[5]Minimal single-element array
nums = [-5,-1,-3], k = 3[-3]All negative numbers, odd k
nums = [-1,-2,3,4], k = 2[-1.5,0.5,3.5]Even k with negative numbers
nums = [2,2,2,2], k = 2[2,2,2]Duplicate values
nums = [1,3,-1,-3,5,3,6,7], k = 4[0,1,1,4,5.5]Larger hand-verified case, even k

Keep reading