Sliding Window Median
Find the median of every window of k readings. nums is a list of readings. Slide a window of k readings from the left end of the list to the right end, one step at a time. For each position, return the median of the readings inside it: the middle reading when k is odd, the average of the two middle readings when k is even. Return one median per position, left to right, as decimals. Limits: 1 <= k <= nums.length <= 100000, and each reading is from -2000000000 to 2000000000. Think about: the two middle readings can add up to well past a 32-bit int. Example: nums = [4,7,1,9,3,6], k = 4 => [5.5, 5.0, 4.5] [4,7,1,9] sorted is 1,4,7,9, so the median is (4 + 7) / 2 = 5.5 [7,1,9,3] sorted is 1,3,7,9, so the median is (3 + 7) / 2 = 5.0 [1,9,3,6] sorted is 1,3,6,9, so the median is (3 + 6) / 2 = 4.5
You're watching a stream of readings through a window of the last k values, and after every step you want the median of what's inside. Interviewers use it to see whether you can keep a running middle while old values drop out, which sorting every window cannot do fast enough. The classic traps are even windows, where the answer is the average of two values, and a sum of two big readings that overflows a 32-bit int. Expect up to 100,000 readings, each up to two billion in size.
Examples
You write
median_sliding_window(nums: List[int], k: int)
Example 1
- Input
- nums = [4,7,1,9,3,6], k = 4
- returns
- [5.5,5.0,4.5]
Example 2
- Input
- nums = [8,-2,5,5,0,-9], k = 1
- returns
- [8.0,-2.0,5.0,5.0,0.0,-9.0]
Save this for your laptop
The editor and Run need a bigger screen. The link opens Sliding Window Median ready to code. It is free, and the editor needs no account.
The pattern behind it
Sliding Window
I reach for it when
- The question asks for the longest, shortest or best stretch of a sequence.
- A rule like "at most k" or "no repeats" decides what counts as valid.
Say this before you type. Say what makes the window valid, and what you do to the left edge when it breaks.
All 9 Sliding Window problemsHeaps
I reach for it when
- You need the k largest or k smallest items.
- You repeatedly take the best remaining item.
Say this before you type. Say what the heap holds, how big it stays, and what sits on top.
All 22 Heaps problems
Meet Coco
Coco is an AI study partner, not a person. She listens while you explain your code, asks what a line does and never hands you the fix. Sign in free to type with Coco, up to a daily limit, and to talk with her for one hour. After that, talking comes with the $79 pack. Anyone can open the editor and run their code.