Sliding Window Median

Problem

The median is the middle value in an ordered integer list. Given an integer array nums and an integer k, there is a sliding window of size k moving from left to right. Return the median array for each window in the original array.

Examples

The brute-force approach

For each window position, copy the k elements, sort them, and return the middle.

result = []
for i in range(len(nums) - k + 1):
    window = sorted(nums[i:i+k])
    if k % 2 == 1:
        result.append(window[k//2])
    else:
        result.append((window[k//2-1] + window[k//2]) / 2)
return result

O(n × k log k) — sorting a k-element window for each of the n-k+1 positions. For large k, this is expensive.

Spotting the pattern

This is a Two Heaps problem. The key question to ask yourself:

If you already know the two-heap solution for stream median, what's the extra operation needed when the window slides?

Answering that is where it clicks, and it's exactly what the guided walkthrough below builds with you: the pattern reasoning, a progressive hint ladder that never spoils the answer, a row-by-row dry run, the optimized solution, and an in-browser editor to run your code against real test cases.