Sliding Window Median (LeetCode 480)
The median of a sorted list of numbers is its middle value; when the list has an even count, there's no single middle entry, so the median is the average of the two values closest to the center.
- For example, the median of
[2,3,4]is3. - For example, the median of
[1,2,3,4]is(2 + 3) / 2 = 2.5.
You're given an integer array nums and a window size k. Slide a window of exactly k consecutive elements across nums, one step at a time from left to right, so that only the numbers currently inside the window are visible.
For every window position, report the window's median. An answer within 10^-5 of the true value is accepted.
Worked Examples
nums = [1,3,-1,-3,5,3,6,7], k = 3[1.00000,-1.00000,-1.00000,3.00000,5.00000,6.00000][1 3 -1] -3 5 3 6 7 1 1 [3 -1 -3] 5 3 6 7 -1 1 3 [-1 -3 5] 3 6 7 -1 1 3 -1 [-3 5 3] 6 7 3 1 3 -1 -3 [5 3 6] 7 5 1 3 -1 -3 5 [3 6 7] 6
nums = [1,2,3,4,2,3,1,4,2], k = 3[2.00000,3.00000,3.00000,3.00000,2.00000,3.00000,2.00000][1,2,3], [2,3,4], [3,4,2], [4,2,3], [2,3,1], [3,1,4], [1,4,2], with medians 2, 3, 3, 3, 2, 3, 2.⚖️Formal Constraints & Bounds
1 <= k <= nums.length <= 105-231 <= nums[i] <= 231 - 1
Core Insight
Dual heap partitioning maintains rolling median parity in O(N log K) time.
Real-World Scenario & Production Applications
Streaming audio noise filtering, financial rolling median moving averages.
Step-by-Step Execution Trace Table
| Window | Elements Sorted | Lower Heap (Small) | Upper Heap (Large) | Median |
|---|---|---|---|---|
| [1, 3, -1] | [-1, 1, 3] | [-1, 1] | [3] | 1.0 |
| [3, -1, -3] | [-3, -1, 3] | [-3, -1] | [3] | -1.0 |
| [-1, -3, 5] | [-3, -1, 5] | [-3, -1] | [5] | -1.0 |
| [-3, 5, 3] | [-3, 3, 5] | [-3, 3] | [5] | 3.0 |
| 1 | small = max-heap (lower half) |
| 2 | large = min-heap (upper half) |
| 3 | push the first k values and balance the heaps |
| 4 | for each next value x: |
| 5 | mark the value that leaves the window as deleted |
| 6 | insert x and balance the heaps |
| 7 | pop deleted values off the heap tops |
| 8 | record the median |
Conceptual Narrative
🧭 Conceptual Foundation & Pattern Intuition
Finding the median of a dynamic stream requires tracking the middle element(s). In a rolling window of fixed size , elements both enter and leave the window at every step. Standard two-pointer sliding windows cannot compute medians because medians depend on sorted value magnitude rather than index position. We maintain two balancing heaps: a max-heap (small) holding the lower elements and a min-heap (large) holding the upper elements. To avoid expensive heap removals when elements slide out of the window, we employ lazy removal: out-of-window elements are marked in a hash map and pruned only when they surface at the heap roots.
🏟️ The Analogy: A Two-Sided Grain Scale with Stale Weights
Picture a balancing scale with two pans: the left pan holds the smaller half of the stones (max-heap, heaviest stone on top), and the right pan holds the larger half (min-heap, lightest stone on top). As the conveyor belt moves:
- An old stone falls off the belt. Instead of digging through the pan to fish it out immediately (which would take time), we tag its serial number on a "stale ledger" (hash map) and adjust our balance count.
- A new stone is placed into the appropriate pan.
- Whenever a tagged stone happens to float to the top of either pan, we simply discard it into the trash in time until a valid, active stone sits at the root.
🔑 Why It Works
The balance invariant is tracked via a net scalar integer balance. When an element is inserted or marked dead, balance increments or decrements. Rebalancing shifts only active elements between heaps, guaranteeing optimal execution without any array shifts!
Direct removal from binary heap: Removing evicted elements directly from standard heaps takes search time, causing overall TLE. Use lazy removal with a frequency hash map for delayed balance pruning.
Stale elements at heap root: Failing to prune balance counts lazily on top of heaps when the root element was already evicted from the sliding window.
Off-by-one in window boundary eviction index: Evicting
nums[i - k]occurs when indexi >= k. Evicting prematurely ati < kcorrupts initial window formation.
4-Phase Thought Process Model
Pattern Recognition Signals
The 10-second spot
Dynamic median computation over a fixed-size moving window.
Formulating the Predicate & Invariants
Turning intuition into a boolean rule
Invariant: len(small) == len(large) or len(small) == len(large) + 1.
Silent Failure Traps & Edge Cases
Where confident candidates still lose points
Re-sorting each window: O(N · K log K) vs optimal
O(N log K).Heap size imbalance causing incorrect median sampling.
The 60-Second Interview Pitch
Say this out loud before you type a single line
"I maintain
small(max-heap) andlarge(min-heap). For each element, I insert and rebalance sizes. Once window sizekis reached, I sample the median from heap roots. Runs inO(N log K)time and O(K) space."
Complexity & Mathematical Proof
O(N log K)
Look at the execution steps: Dual balanced heaps with lazy deletion hash table for elements exiting window of size K. Each element addition and eviction costs O(log K). Total N steps.
O(K) Auxiliary
Look at memory allocations: Call stack uses O(1) Iterative. Dual heaps and lazy deletion hash map store at most O(K) active and invalid elements.
T(N, K) = N · O(log K) = O(N log K)
Derivation Progression
O(log K) heap insertion
Inserts new element into dual heaps.
delayed[out_val] += 1
Marks departing element in hash map in O(1).
O(log K) amortized heap pops
Prunes invalid roots lazily and rebalances sizes.
Variable Definitions
Total number of elements in the array
Sliding window size
Memory Architecture & Bounds
O(1) Iterative
O(K) Dual heaps and lazy deletion hash map
O(N - K + 1) Float median array
Boundary Best / Worst Cases
Binary Heap Priority Queue Tree
Senior SWE Deconstruction & Hardware Caveats
Triggers: "median of each sliding window of size k". Naive removal of an outgoing element from a heap is , giving overall time. A Senior SWE employs Dual Heaps with Lazy Deletion: maintain an auxiliary hash map delayed = defaultdict(int) counting elements that have exited the window, pruning them lazily only when they surface at the top of either heap!
. Time budget is strictly , scaling comfortably across iterations.
Size bookkeeping: len(small) reflects raw array size including dead elements, NOT valid window elements. Tracking small_size and large_size independently is mandatory for accurate rebalancing.
Sliding Window Median (LeetCode 480)
The median of a sorted list of numbers is its middle value; when the list has an even count, there's no single middle entry, so the median is the average of the two values closest to the center.
- For example, the median of
[2,3,4]is3. - For example, the median of
[1,2,3,4]is(2 + 3) / 2 = 2.5.
You're given an integer array nums and a window size k. Slide a window of exactly k consecutive elements across nums, one step at a time from left to right, so that only the numbers currently inside the window are visible.
For every window position, report the window's median. An answer within 10^-5 of the true value is accepted.
Worked Examples
nums = [1,3,-1,-3,5,3,6,7], k = 3[1.00000,-1.00000,-1.00000,3.00000,5.00000,6.00000][1 3 -1] -3 5 3 6 7 1 1 [3 -1 -3] 5 3 6 7 -1 1 3 [-1 -3 5] 3 6 7 -1 1 3 -1 [-3 5 3] 6 7 3 1 3 -1 -3 [5 3 6] 7 5 1 3 -1 -3 5 [3 6 7] 6
nums = [1,2,3,4,2,3,1,4,2], k = 3[2.00000,3.00000,3.00000,3.00000,2.00000,3.00000,2.00000][1,2,3], [2,3,4], [3,4,2], [4,2,3], [2,3,1], [3,1,4], [1,4,2], with medians 2, 3, 3, 3, 2, 3, 2.⚖️Formal Constraints & Bounds
1 <= k <= nums.length <= 105-231 <= nums[i] <= 231 - 1
Core Insight
Dual heap partitioning maintains rolling median parity in O(N log K) time.
Real-World Scenario & Production Applications
Streaming audio noise filtering, financial rolling median moving averages.
Step-by-Step Execution Trace Table
| Window | Elements Sorted | Lower Heap (Small) | Upper Heap (Large) | Median |
|---|---|---|---|---|
| [1, 3, -1] | [-1, 1, 3] | [-1, 1] | [3] | 1.0 |
| [3, -1, -3] | [-3, -1, 3] | [-3, -1] | [3] | -1.0 |
| [-1, -3, 5] | [-3, -1, 5] | [-3, -1] | [5] | -1.0 |
| [-3, 5, 3] | [-3, 3, 5] | [-3, 3] | [5] | 3.0 |
| 1 | small = max-heap (lower half) |
| 2 | large = min-heap (upper half) |
| 3 | push the first k values and balance the heaps |
| 4 | for each next value x: |
| 5 | mark the value that leaves the window as deleted |
| 6 | insert x and balance the heaps |
| 7 | pop deleted values off the heap tops |
| 8 | record the median |
Conceptual Narrative
🧭 Conceptual Foundation & Pattern Intuition
Finding the median of a dynamic stream requires tracking the middle element(s). In a rolling window of fixed size , elements both enter and leave the window at every step. Standard two-pointer sliding windows cannot compute medians because medians depend on sorted value magnitude rather than index position. We maintain two balancing heaps: a max-heap (small) holding the lower elements and a min-heap (large) holding the upper elements. To avoid expensive heap removals when elements slide out of the window, we employ lazy removal: out-of-window elements are marked in a hash map and pruned only when they surface at the heap roots.
🏟️ The Analogy: A Two-Sided Grain Scale with Stale Weights
Picture a balancing scale with two pans: the left pan holds the smaller half of the stones (max-heap, heaviest stone on top), and the right pan holds the larger half (min-heap, lightest stone on top). As the conveyor belt moves:
- An old stone falls off the belt. Instead of digging through the pan to fish it out immediately (which would take time), we tag its serial number on a "stale ledger" (hash map) and adjust our balance count.
- A new stone is placed into the appropriate pan.
- Whenever a tagged stone happens to float to the top of either pan, we simply discard it into the trash in time until a valid, active stone sits at the root.
🔑 Why It Works
The balance invariant is tracked via a net scalar integer balance. When an element is inserted or marked dead, balance increments or decrements. Rebalancing shifts only active elements between heaps, guaranteeing optimal execution without any array shifts!
Direct removal from binary heap: Removing evicted elements directly from standard heaps takes search time, causing overall TLE. Use lazy removal with a frequency hash map for delayed balance pruning.
Stale elements at heap root: Failing to prune balance counts lazily on top of heaps when the root element was already evicted from the sliding window.
Off-by-one in window boundary eviction index: Evicting
nums[i - k]occurs when indexi >= k. Evicting prematurely ati < kcorrupts initial window formation.
4-Phase Thought Process Model
Pattern Recognition Signals
The 10-second spot
Dynamic median computation over a fixed-size moving window.
Formulating the Predicate & Invariants
Turning intuition into a boolean rule
Invariant: len(small) == len(large) or len(small) == len(large) + 1.
Silent Failure Traps & Edge Cases
Where confident candidates still lose points
Re-sorting each window: O(N · K log K) vs optimal
O(N log K).Heap size imbalance causing incorrect median sampling.
The 60-Second Interview Pitch
Say this out loud before you type a single line
"I maintain
small(max-heap) andlarge(min-heap). For each element, I insert and rebalance sizes. Once window sizekis reached, I sample the median from heap roots. Runs inO(N log K)time and O(K) space."
Complexity & Mathematical Proof
O(N log K)
Look at the execution steps: Dual balanced heaps with lazy deletion hash table for elements exiting window of size K. Each element addition and eviction costs O(log K). Total N steps.
O(K) Auxiliary
Look at memory allocations: Call stack uses O(1) Iterative. Dual heaps and lazy deletion hash map store at most O(K) active and invalid elements.
T(N, K) = N · O(log K) = O(N log K)
Derivation Progression
O(log K) heap insertion
Inserts new element into dual heaps.
delayed[out_val] += 1
Marks departing element in hash map in O(1).
O(log K) amortized heap pops
Prunes invalid roots lazily and rebalances sizes.
Variable Definitions
Total number of elements in the array
Sliding window size
Memory Architecture & Bounds
O(1) Iterative
O(K) Dual heaps and lazy deletion hash map
O(N - K + 1) Float median array
Boundary Best / Worst Cases
Binary Heap Priority Queue Tree
Senior SWE Deconstruction & Hardware Caveats
Triggers: "median of each sliding window of size k". Naive removal of an outgoing element from a heap is , giving overall time. A Senior SWE employs Dual Heaps with Lazy Deletion: maintain an auxiliary hash map delayed = defaultdict(int) counting elements that have exited the window, pruning them lazily only when they surface at the top of either heap!
. Time budget is strictly , scaling comfortably across iterations.
Size bookkeeping: len(small) reflects raw array size including dead elements, NOT valid window elements. Tracking small_size and large_size independently is mandatory for accurate rebalancing.