How to Solve Sliding Window Median

This problem requires calculating the median of every contiguous subarray of length k while sliding across nums. The key is maintaining a data structure that allows efficient median retrieval and fast insertion/removal as the window moves. Using a combination of max-heap, min-heap, and hash-based delayed deletion enables O(log k) updates and median queries for each step.

Problem Statement

Given an integer array nums and an integer k, a sliding window of size k moves from left to right across the array. For each window position, you must determine the median of the numbers currently in the window. The median is defined as the middle value of the ordered list; if the list has even length, the median is the mean of the two middle values.

Return an array of medians corresponding to each sliding window as it moves across nums. Each time the window moves one position to the right, update the median efficiently. Answers within 10^-5 of the actual median are acceptable. 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.00000,-1.00000,-1.00000,3.00000,5.00000,6.00000]

Window position Median

---

[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

Example 2

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

Output: [2.00000,3.00000,3.00000,3.00000,2.00000,3.00000,2.00000]

Example details omitted.

Constraints

• 1 <= k <= nums.length <= 105
• -231 <= nums[i] <= 231 - 1

Solution Approach

Use dual heaps for efficient median maintenance

Maintain a max-heap for the lower half and a min-heap for the upper half of the current window. Ensure the heaps are balanced so that median retrieval is immediate. This avoids re-sorting the window at every step and keeps operations logarithmic in k.

Incorporate hash map for delayed deletion

Since heaps do not support O(log k) arbitrary deletions, track numbers that need removal in a hash map. When the top of a heap is invalid, remove it lazily. This technique ensures that window shifts maintain heap integrity without full rebuilds.

Slide the window with update logic

For each step, insert the incoming number into the appropriate heap and mark the outgoing number for removal. Rebalance heaps if necessary and read the median from the top elements. Repeat until the window reaches the array's end.

Complexity Analysis

Time complexity is O(n log k) due to insertion and deletion in heaps for each of the n-k+1 windows. Space complexity is O(k) for the two heaps and hash map storing delayed deletions.

What Interviewers Usually Probe

• Will you maintain the sorted order of the window explicitly or implicitly?
• How do you handle deletions from a heap efficiently when the window moves?
• Can you explain why dual heaps are necessary instead of a single priority queue?

Common Pitfalls or Variants

Common pitfalls

• Attempting to sort the window each step, leading to O(n k log k) time.
• Forgetting to rebalance heaps after insertions and deletions, causing incorrect median computation.
• Not accounting for even-length windows where median is the average of two middle numbers.

Follow-up variants

• Compute the median in a circular sliding window where the array wraps around.
• Find the k-th smallest element in each sliding window instead of the median.
• Handle dynamic updates to nums in addition to sliding the window.

How GhostInterview Helps

• Automatically manages heap insertion, deletion, and rebalancing to maintain current window median.
• Highlights where delayed deletion via hash map prevents O(k) operations at each step.
• Provides immediate verification of medians for each window, ensuring correctness under edge cases.

Topic Pages

• Array
• Hash Table
• Sliding Window
• Heap (Priority Queue)

Related GhostInterview Pages

• LeetCode Interview Copilot - Use GhostInterview as a live solver when you want direct help with LeetCode-style coding questions.
• Coding Interview Assistant - See how GhostInterview supports array, string, linked list, graph, and tree interview workflows.
• How GhostInterview Works - Review the screenshot, reasoning, and answer flow before using the solver in a live interview.

FAQ

What data structure pattern is essential for Sliding Window Median?

Dual heaps (max-heap and min-heap) combined with a hash map for lazy deletions form the core pattern to retrieve medians efficiently.

How do I handle even-sized windows?

For even-length windows, compute the median as the average of the top of the max-heap and min-heap after rebalancing.

Is sorting each window a valid approach?

Sorting each window works but is inefficient; it leads to O(n k log k) time complexity and fails for large arrays.

How do hash maps assist heaps in this problem?

Hash maps track elements marked for removal, allowing heaps to lazily remove outdated values without costly re-heapification.

Can Sliding Window Median be solved with a single heap?

A single heap cannot efficiently provide median while supporting arbitrary deletions; dual heaps are required to maintain balance.