Sliding Window Median - Video Solutions

Problem Overview: You are given an integer array and a window size k. As the window slides one step to the right, compute the median of the current window. The challenge is maintaining the median efficiently while elements enter and leave the window.

Approach 1: Brute Force (O(n * k log k) time, O(k) space)

The most direct approach recomputes the median for every window. Extract the k elements in the current window, sort them, and read the middle element (or the average of two middle elements for even k). Sorting costs O(k log k) per window and there are about n - k + 1 windows, resulting in O(n * k log k) time. Space complexity is O(k) to hold the temporary window. This approach is easy to implement and useful for verifying correctness, but it becomes slow when k grows large.

Approach 2: Dual Heap Approach (O(n log k) time, O(k) space)

This is the standard optimal solution. Maintain two heaps: a max heap for the smaller half of numbers and a min heap for the larger half. The heaps stay balanced so their sizes differ by at most one, allowing the median to be read directly from the heap tops. When the window slides, insert the new element and lazily remove the outgoing element using a hash map to track delayed deletions. Each insertion or removal costs O(log k), so processing all elements takes O(n log k) time. This technique combines heap (priority queue) operations with a small hash table for efficient cleanup.

Approach 3: Heap-Based Sliding Window with Lazy Deletion (O(n log k) time, O(k) space)

A variation of the dual heap approach explicitly focuses on lazy deletion. Instead of removing elements immediately when they fall out of the window, mark them in a map and clean them only when they appear at the top of a heap. This avoids expensive arbitrary deletions from a heap. The heaps maintain balance as elements are inserted and invalid ones are popped. Median lookup remains O(1). This method is widely used in competitive programming for sliding window median problems.

Approach 4: Multiset and Iterator (O(n log k) time, O(k) space)

Languages with ordered containers (like multiset in C++ or TreeSet-like structures) allow a different strategy. Store the current window in a balanced binary search tree and maintain an iterator pointing to the median element. When the window moves, insert the incoming value and erase the outgoing one while adjusting the iterator accordingly. Both operations take O(log k). Accessing the median becomes constant time. This approach is clean and deterministic but relies on ordered-set support.

Recommended for interviews: The dual heap approach is what most interviewers expect. It demonstrates understanding of heap balancing, lazy deletion, and sliding window optimization. Showing the brute force first proves you understand the problem, but implementing the O(n log k) heap solution demonstrates strong data structure skills.