We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Sliding Window Median

Difficulty: Hard

Problem Description

You are given an integer array nums and an integer k. There is a sliding window of size k which is moving from the very left of the array to the very right. You can only see the k numbers in the window. Each time the sliding window moves right by one position. Return the median array for each window in the original array. Answers within 10^-5 of the actual value will be accepted.

Key Insights

  • The median is the middle value in an ordered list; for an even size, it is the mean of the two middle values.
  • A sliding window approach allows us to manage the current subset of the array efficiently.
  • Using two heaps (a max-heap and a min-heap) allows us to keep track of the median efficiently as the window slides.

Space and Time Complexity

Time Complexity: O(n log k)
Space Complexity: O(k)

Solution

To solve the problem of finding the median in a sliding window, we can utilize two heaps:

  1. A max-heap to store the lower half of the numbers.
  2. A min-heap to store the upper half of the numbers.

As we slide the window:

  • We add the new element to the appropriate heap.
  • We balance the heaps to ensure the max-heap always has the same number or one more element than the min-heap.
  • The median can then be calculated based on the sizes and top elements of the heaps.

This approach allows us to efficiently compute the median for each window position.

Code Solutions

import heapq

def medianSlidingWindow(nums, k):
    def add_num(num):
        # Add to max-heap (lower half)
        heapq.heappush(max_heap, -num)
        
        # Balance the heaps
        if max_heap and (-max_heap[0] > min_heap[0]):
            heapq.heappush(min_heap, -heapq.heappop(max_heap))
        
        # Maintain the size of heaps
        if len(max_heap) > len(min_heap) + 1:
            heapq.heappush(min_heap, -heapq.heappop(max_heap))
        if len(min_heap) > len(max_heap):
            heapq.heappush(max_heap, -heapq.heappop(min_heap))
    
    def find_median():
        if len(max_heap) > len(min_heap):
            return float(-max_heap[0])
        return (-max_heap[0] + min_heap[0]) / 2
    
    max_heap = []  # max-heap for the lower half
    min_heap = []  # min-heap for the upper half
    result = []
    
    for i in range(len(nums)):
        add_num(nums[i])
        if i >= k - 1:
            result.append(find_median())
            # Remove the element that is sliding out of the window
            outgoing = nums[i - k + 1]
            if outgoing <= -max_heap[0]:
                max_heap.remove(-outgoing)
                heapq.heapify(max_heap)
            else:
                min_heap.remove(outgoing)
                heapq.heapify(min_heap)
    
    return result
← Back to All Questions