Module 5 · Median Pattern

Sliding Window Median

HardProblem 11 of 14 12 min read ~40 min to solve LeetCode

HeapPriority QueueTwo HeapsSliding WindowLazy Deletion

Asked atGoogleAmazonMetaMicrosoftBloombergApple

Problem Statement

Given an integer array nums and an integer k, move a window of size k from left to right across the array. Return an array where each entry is the median of the current window. If k is even, the median is the average of the two middle values.

Input

An integer array nums and a window size k.

Output

A double array containing the median for every contiguous window of length k, in left-to-right order.

Constraints

•1 <= k <= nums.length <= 10^5
•-2^31 <= nums[i] <= 2^31 - 1

Examples

Example 1

Input:

nums = [1,3,-1,-3,5,3,6,7], k = 3

Output: [1.0,-1.0,-1.0,3.0,5.0,6.0]

Explanation: The first window [1,3,-1] has median 1. As the window slides, each outgoing value is removed logically and each incoming value is added before reading the next median.

Example 2

Input:

nums = [1,2,3,4], k = 2

Output: [1.5,2.5,3.5]

Explanation: Every window has two values, so each median is the average of its two sorted middle values.

Learning Objectives

Extend the two-heaps median pattern from a growing stream to a fixed-size window.
Use lazy deletion to avoid O(k) arbitrary removal from Java **PriorityQueue**.
Maintain logical heap sizes separately from physical heap contents.
Compute even-length medians with **long** or **double** arithmetic to avoid integer overflow.

Intuition

Pattern Recognition

The prompt combines two signals: median queries and a sliding window. The median signal suggests the same lower-half max-heap and upper-half min-heap split. The sliding-window signal adds deletion, because the oldest value leaves when a new value enters.

The trap is calling PriorityQueue.remove(value) on every slide. That searches the heap linearly, destroying the intended complexity. Lazy deletion fixes this: when a value leaves the window, record it in a delayed-removal map and decrement the logical size of the heap it belongs to. The actual heap node is removed only when it reaches the root, right before a root would be trusted for a rebalance or median.

Common mistakes

×Using **PriorityQueue.remove(value)** for the outgoing element, which costs O(k) per slide.
×Counting stale delayed elements in heap sizes after they have left the window logically.
×Reading **peek()** without first pruning delayed roots from that heap.
×Averaging two **int** roots directly, which can overflow before becoming a double.

Algorithm Explanation

Key idea

Use low, a max-heap for the lower half of the current window, and high, a min-heap for the upper half. Track lowSize and highSize as counts of valid window elements, excluding values scheduled in the delayed-removal map. The invariant after every slide is lowSize >= highSize and lowSize - highSize <= 1. For odd k, low holds one extra valid value and its root is the median. For even k, average the two roots using long or double arithmetic. A TreeMap or two-multiset approach can also remove by key in O(log k), but lazy deletion keeps the implementation close to the PriorityQueue version of running median.

Heap walkthrough

Use nums = [1,3,-1,-3,5,3] and k = 3. Build the first window by adding 1, 3, and -1: low = [1,-1], high = [3], median 1. Slide right by adding -3; it enters low, then root 1 moves to high because low is too large: low = [-1,-3], high = [1,3]. Now outgoing 1 is scheduled in the delayed map. Since it is at the high root, prune it immediately, leaving high = [3] and median -1. Next add 5 into high, then schedule outgoing 3. Because 3 is the high root, prune it and keep low = [-1,-3], high = [5], median -1. Next add 3 into high and schedule outgoing -1. The outgoing -1 is at the low root, so pruning removes it, then rebalancing moves 3 from high to low. The heaps become low = [3,-3], high = [5], median 3.

Algorithm

Initialise low, high, a delayed count map, and logical sizes lowSize and highSize.
Add the first k numbers with the normal two-heap insertion and rebalance after each add.
Record the first median from the valid heap roots.
For each next index, add the incoming value, then schedule the outgoing value in delayed.
Decrement lowSize if the outgoing value is <= low.peek(), otherwise decrement highSize.
Prune a heap while its root has a positive delayed count.
Rebalance until lowSize >= highSize and lowSize - highSize <= 1, pruning roots after moving between heaps.
Record the next median from low.peek() or the average of both roots.

Solutions

Solution: Two heaps with lazy deletion

When to prefer this:

Use this when the language heap supports fast root removal but not fast arbitrary deletion. In Java, PriorityQueue needs the delayed map to keep every slide logarithmic amortized.

The structure is the running-median design plus a delayed-removal map. Values that leave the window are marked stale and removed only when they reach the top of a heap. Logical sizes drive balancing; physical heap sizes may temporarily include stale values below the root.

Step-by-step

Add the first k values using the same two-heap insertion as MedianFinder.
For each slide, add the incoming value and mark the outgoing value in delayed.
Decide which logical size to decrement by comparing the outgoing value with low.peek().
Prune delayed roots from any heap before trusting its root.
Rebalance by moving roots until low has either the same valid size as high or one extra valid value.
Write the median as low.peek() for odd k, or as ((long) low.peek() + (long) high.peek()) / 2.0 for even k.

Time

O(n log k)

Space

O(k) logical window state, O(n) worst-case lazy heap storage

Each add and root move costs O(log k) logically; stale values are pruned when they surface at a root.

Java implementation

Loading…

Dry Run

Sample input

nums = [1,3,-1,-3,5,3], k = 3. Heaps show valid values after pruning delayed roots, with low allowed one extra value.

op	low	high	median
add 1	[1]	[]	window incomplete
add 3	[1]	[3]	window incomplete
add -1	[1,-1]	[3]	1.0
add -3, remove 1	[-1,-3]	[3]	-1.0
add 5, remove 3	[-1,-3]	[5]	-1.0
add 3, remove -1	[3,-3]	[5]	3.0

The delayed map lets removal wait until a stale value reaches a heap root. Each recorded median is read only after pruning and rebalancing restore the valid two-heap split.

Interview Tips

Separate physical heap contents from logical window contents. The interviewer wants to hear that lowSize and highSize ignore delayed values, and that peek() is safe only after pruning stale roots. Also mention the balanced-tree alternative: two TreeMaps or multisets remove outgoing values directly in O(log k), often with cleaner space bounds but more bookkeeping.

Likely follow-ups

How would a TreeMap-based two-multiset solution differ from lazy deletion?
How would you support a variable window size where **k** changes over time?
How would you return the lower median instead of the average for even windows?
How would you handle a stream so large that stale heap entries must be periodically compacted?

Key Takeaways

Sliding-window median is running median plus deletion.
Java **PriorityQueue** needs lazy deletion because arbitrary removal is not logarithmic.
Logical heap sizes, not physical sizes, maintain the balance invariant.
Use **long** or **double** before averaging two roots to avoid overflow.

Reusable template: Sliding two heaps with lazy deletion: add the incoming value, mark the outgoing value delayed, prune stale roots, rebalance valid sizes, and read the median from the roots.