480. Sliding Window Median - Detailed Explanation

Problem Statement

Given an integer array nums and a sliding window of size k, you must move the window from the leftmost side of the array to the rightmost side. For each position of the sliding window, you need to calculate the median of the elements within the window. The median is defined as the middle element after sorting if the number of elements is odd, or the average of the two middle elements if the number of elements is even. Return an array of medians corresponding to each window position.

For example, if nums = [1,3,-1,-3,5,3,6,7] and k = 3, the medians for each sliding window would be:

• Window [1, 3, -1] → median is 1
• Window [3, -1, -3] → median is -1
• Window [-1, -3, 5] → median is -1
• Window [-3, 5, 3] → median is 3
• Window [5, 3, 6] → median is 5
• Window [3, 6, 7] → median is 6

Hints

1. Two Heaps Method:
   To efficiently calculate the median, consider using two heaps:

   • A max-heap to maintain the lower half of numbers.
   • A min-heap to maintain the upper half of numbers. This allows you to retrieve the middle element(s) quickly.

2. Balancing Heaps:
   Keep the heaps balanced so that their sizes differ by at most one. When the window size is odd, one heap will contain one extra element, and that top element is the median. When the window size is even, the median is the average of the tops of both heaps.

3. Lazy Deletion:
   As the window slides, numbers leave the window. Removing an element directly from a heap is inefficient. Use a lazy deletion strategy by marking elements for removal and cleaning them up when they reach the top of the heap.

Approaches

Brute Force Approach

• Idea:
  For every window, sort the k elements and then calculate the median.
• Drawback:
  Sorting each window takes O(k log k) time and doing this for each window results in O(n k log k) time, which is inefficient for large n.

Optimal Approach: Two Heaps with Lazy Deletion

• Idea:
  Use a max-heap and a min-heap to keep track of the lower and upper halves of the window elements, respectively. When a new element enters the window, add it to one of the heaps (and balance if needed). When an element leaves, mark it for deletion and remove it lazily.
• Steps:

  1. Insertion:
     Insert the incoming number into the appropriate heap. Balance the heaps if necessary.

  2. Removal:
     Instead of directly removing the outgoing number (which can be inefficient), record its occurrence in a hash map. When the top of a heap is marked as deleted, remove it.

  3. Median Calculation:
     If k is odd, the median is the top of the max-heap. If k is even, the median is the average of the tops of the max-heap and min-heap.

  4. Sliding the Window:
     Move the window by one position, update heaps for the new element and mark the element leaving the window for lazy deletion.

Complexity Analysis

• Time Complexity:
  Insertion and deletion in heaps take O(log k) time. Each of the n - k + 1 windows requires O(log k) operations, resulting in an overall time complexity of O(n log k).

• Space Complexity:
  Two heaps store at most k elements, and the lazy deletion map holds at most k elements, resulting in O(k) space.

Python Code