#480

Hard

auto_awesomeArray scanning plus hash lookup

LeetCode Problem Workspace

Sliding Window Median

Compute the median for each sliding window of size k in an array using efficient array scanning and hash lookup techniques.

array hash table sliding window heap priority queue

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

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

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.

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.

terminal

Solution

Solution 1: Dual Priority Queues (Min-Heap and Max-Heap) + Lazy Deletion

We can use two priority queues (min-heap and max-heap) to maintain the elements in the current window. One priority queue stores the smaller half of the elements, and the other priority queue stores the larger half of the elements. This way, the median of the current window is either the average of the top elements of the two heaps or one of the top elements.

class MedianFinder:
    def __init__(self, k: int):
        self.k = k
        self.small = []
        self.large = []
        self.delayed = defaultdict(int)
        self.small_size = 0
        self.large_size = 0

    def add_num(self, num: int):
        if not self.small or num <= -self.small[0]:
            heappush(self.small, -num)
            self.small_size += 1
        else:
            heappush(self.large, num)
            self.large_size += 1
        self.rebalance()

    def find_median(self) -> float:
        return -self.small[0] if self.k & 1 else (-self.small[0] + self.large[0]) / 2

    def remove_num(self, num: int):
        self.delayed[num] += 1
        if num <= -self.small[0]:
            self.small_size -= 1
            if num == -self.small[0]:
                self.prune(self.small)
        else:
            self.large_size -= 1
            if num == self.large[0]:
                self.prune(self.large)
        self.rebalance()

    def prune(self, pq: List[int]):
        sign = -1 if pq is self.small else 1
        while pq and sign * pq[0] in self.delayed:
            self.delayed[sign * pq[0]] -= 1
            if self.delayed[sign * pq[0]] == 0:
                self.delayed.pop(sign * pq[0])
            heappop(pq)

    def rebalance(self):
        if self.small_size > self.large_size + 1:
            heappush(self.large, -heappop(self.small))
            self.small_size -= 1
            self.large_size += 1
            self.prune(self.small)
        elif self.small_size < self.large_size:
            heappush(self.small, -heappop(self.large))
            self.large_size -= 1
            self.small_size += 1
            self.prune(self.large)


class Solution:
    def medianSlidingWindow(self, nums: List[int], k: int) -> List[float]:
        finder = MedianFinder(k)
        for x in nums[:k]:
            finder.add_num(x)
        ans = [finder.find_median()]
        for i in range(k, len(nums)):
            finder.add_num(nums[i])
            finder.remove_num(nums[i - k])
            ans.append(finder.find_median())
        return ans

Solution 2: Ordered Set

We can use two ordered sets to maintain the elements in the current window. The ordered set $l$ stores the smaller half of the elements in the current window, and the ordered set $r$ stores the larger half of the elements.

class MedianFinder:
    def __init__(self, k: int):
        self.k = k
        self.small = []
        self.large = []
        self.delayed = defaultdict(int)
        self.small_size = 0
        self.large_size = 0

    def add_num(self, num: int):
        if not self.small or num <= -self.small[0]:
            heappush(self.small, -num)
            self.small_size += 1
        else:
            heappush(self.large, num)
            self.large_size += 1
        self.rebalance()

    def find_median(self) -> float:
        return -self.small[0] if self.k & 1 else (-self.small[0] + self.large[0]) / 2

    def remove_num(self, num: int):
        self.delayed[num] += 1
        if num <= -self.small[0]:
            self.small_size -= 1
            if num == -self.small[0]:
                self.prune(self.small)
        else:
            self.large_size -= 1
            if num == self.large[0]:
                self.prune(self.large)
        self.rebalance()

    def prune(self, pq: List[int]):
        sign = -1 if pq is self.small else 1
        while pq and sign * pq[0] in self.delayed:
            self.delayed[sign * pq[0]] -= 1
            if self.delayed[sign * pq[0]] == 0:
                self.delayed.pop(sign * pq[0])
            heappop(pq)

    def rebalance(self):
        if self.small_size > self.large_size + 1:
            heappush(self.large, -heappop(self.small))
            self.small_size -= 1
            self.large_size += 1
            self.prune(self.small)
        elif self.small_size < self.large_size:
            heappush(self.small, -heappop(self.large))
            self.large_size -= 1
            self.small_size += 1
            self.prune(self.large)


class Solution:
    def medianSlidingWindow(self, nums: List[int], k: int) -> List[float]:
        finder = MedianFinder(k)
        for x in nums[:k]:
            finder.add_num(x)
        ans = [finder.find_median()]
        for i in range(k, len(nums)):
            finder.add_num(nums[i])
            finder.remove_num(nums[i - k])
            ans.append(finder.find_median())
        return ans

Continue Practicing

#632 smallest range covering elements from k lists #594 longest harmonious subsequence #347 top k frequent elements