Sliding Window Median LeetCode 480 Guide

LeetCode 480 gives you an integer array nums and a window size k. As the window slides from left to right one position at a time, you must return the median of the k elements currently inside the window. The result is an array of n - k + 1 medians, one per window position.

The median follows the standard definition: for odd k, it is the middle element of the sorted window; for even k, it is the average of the two middle elements. For example with nums = [1,3,-1,-3,5,3,6,7] and k = 3, the output is [1,-1,-1,3,5,6] — one median per window slide.

Key constraints: nums length up to 100,000, window size k between 1 and nums.length, and values in range [-2^31, 2^31 - 1]. The challenge is that a brute-force O(n·k) approach sorting the window on every slide will time out for large inputs.

LeetCode 295 Find Median from Data Stream only ever adds elements. The two-heap approach works beautifully there because heaps support fast insertion and the median is always accessible at the top. Sliding window median adds a new challenge: elements leave the window as it slides, and heaps do not natively support arbitrary deletion.

When the window moves right, the element at the left edge falls out. If it happened to be sitting near the top of one of your heaps, you need to remove it — but heap removal of arbitrary elements is O(n). Doing that on every slide would be O(n^2) overall, worse than brute force sorting.

The key insight is that you do not have to remove the element immediately. Instead, you can mark it as "deleted" and skip it when it eventually rises to the top of the heap. This technique is called lazy deletion, and it lets you keep O(log n) amortized cost per slide.

The heap structure mirrors LeetCode 295 exactly: a max-heap holds the lower half of the current window, and a min-heap holds the upper half. The top of the max-heap is the largest small element; the top of the min-heap is the smallest large element. For odd k the max-heap holds one extra element and its top is the median; for even k the median is the average of both tops.

The balance invariant is the same: the max-heap size must always equal or exceed the min-heap size by at most one. After every add and every deletion, you rebalance if the sizes drift apart. Because Python's heapq is a min-heap only, negate values to simulate a max-heap for the lower half.

The difference from LeetCode 295 is that here we process a fixed-length stream: each step we add the incoming element on the right and remove the outgoing element on the left. Both operations must maintain the heap invariant and both must be fast.

Lazy deletion works by maintaining a hash map (to_delete) that records how many times each value needs to be removed. When an element exits the window, increment its count in to_delete rather than touching the heap. The heap still contains that element, but it is now "virtually" absent.

To account for these phantom elements, track separate "virtual" size counters for each heap. When you add a new element, increment the virtual size of whichever heap it lands in. When you mark an element for deletion, decrement the virtual size of the heap it belongs to. The virtual sizes drive the rebalancing logic — not the actual heap lengths.

Cleanup happens lazily: before reading the median, check if the top of each heap is in to_delete. If it is, pop it and decrement its to_delete count until the top is a valid element. This cleanup cost is amortized across all operations because each element enters and exits the to_delete map exactly once.

Each window slide has two parts: add the new right element, then mark the old left element for lazy deletion. After both, rebalance the virtual sizes so the invariant holds. If the max-heap virtual size is too large, move its true top to the min-heap. If the min-heap virtual size exceeds the max-heap, move its true top to the max-heap.

After rebalancing, clean the tops of both heaps by popping any elements that appear in to_delete. This ensures that when you read the median, both tops are valid elements. The clean step may pop multiple items in rare cases, but each item is cleaned at most once across all slides.

Putting it together: (1) push new element to the appropriate heap, update virtual sizes; (2) mark outgoing element in to_delete, update virtual sizes; (3) rebalance virtual sizes with at most one heap move; (4) clean tops of both heaps; (5) read median from tops. Steps 3-5 are the unique additions over the LeetCode 295 approach.

In Python, the cleanest approach uses SortedList from the sortedcontainers library. SortedList maintains sorted order and supports O(log k) add and O(log k) remove. For each window slide: add the new element with sl.add(x), remove the outgoing element with sl.remove(nums[i-k]), then read sl[k//2] for odd k or the average of sl[k//2 - 1] and sl[k//2] for even k. No lazy deletion needed — SortedList handles arbitrary removal directly.

The heap-with-lazy-deletion approach is O(n log n) time and O(n) space. SortedList is also O(n log n) time and O(k) space since you only store the current window. In a real interview, either approach is acceptable — but knowing the heap version demonstrates deeper understanding of heap internals and lazy deletion as a general technique.

In Java, TreeMap works similarly to SortedList: use two TreeMaps (lower and upper) with custom comparators to break ties. Track counts to handle duplicate values correctly. Alternatively, implement the lazy deletion heap approach using two PriorityQueues and a HashMap<Integer, Integer> for the to_delete counts.

Find Median from Data Stream (LeetCode 295) is the direct predecessor — master the two-heap balance invariant there first before tackling the sliding window variant. The mental model is identical; lazy deletion is the only new concept added in LeetCode 480.

Sliding Window Maximum (LeetCode 239) solves the simpler case of tracking the maximum (not median) of a sliding window using a monotonic deque in O(n) time. It is a good warmup for thinking about what element to remove as the window slides, without the complexity of median tracking.

The two-heap pattern appears in several other hard problems: IPO (LeetCode 502), Find Right Interval (LeetCode 436), and The Skyline Problem (LeetCode 218). Lazy deletion itself is also used in scheduling problems where you need a priority queue but events can be cancelled before they are processed.