{x}
blog image

Sliding Window Median

The median is the middle value in an ordered integer list. If the size of the list is even, there is no middle value. So the median is the mean of the two middle values.

  • For examples, if arr = [2,3,4], the median is 3.
  • For examples, if arr = [1,2,3,4], the median is (2 + 3) / 2 = 2.5.

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.

 

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]
Explanation: 
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]

 

Constraints:

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

Solution Explanation for Sliding Window Median

This problem requires finding the median of all sliding windows of size k within a given array nums. The solutions below leverage efficient data structures to achieve a time complexity better than brute force.

Approach 1: Dual Priority Queues (Min-Heap and Max-Heap)

This approach uses two heaps: a min-heap (large) to store the larger half of the window's elements and a max-heap (small) to store the smaller half. Maintaining these heaps allows for efficient median calculation. The median is either the top of the small heap (if k is odd) or the average of the tops of both heaps (if k is even).

The challenge lies in efficiently removing elements from the sliding window as it moves. Simple heap deletion is O(n log k) which is not optimal. To address this, a lazy deletion technique is employed. Elements to be removed are marked in a delayed dictionary instead of being immediately removed from the heaps. The heaps are periodically pruned to remove these marked elements, trading some efficiency for a simpler implementation. This keeps the asymptotic time complexity optimal.

Time Complexity: O(N log k), where N is the length of nums and k is the window size. Each element is added and removed (lazily) from the heaps at most once. Heap operations are O(log k).

Space Complexity: O(k), as the heaps store at most k elements, and the delayed dictionary also holds a limited number of elements.

Approach 2: Ordered Sets (Sorted Lists/Trees)

This approach uses two ordered sets (l and r). l stores the smaller half of the window, and r stores the larger half. The ordered sets ensure efficient retrieval of median values.

Adding a new element to the window involves adding it to r, then moving the smallest element from r to l. The sets are then balanced (if l has more than one element than r) by moving the largest from l to r. The median is found by looking at the top/bottom of l and r based on whether k is even or odd.

Removing elements from the left edge of the sliding window is handled by removing the element from either l or r, and then rebalancing again. Ordered Sets provide O(log k) time for addition and deletion and thus, the complexity is better than using simple arrays.

Time Complexity: O(N log k) The operations on the ordered sets (insertion, deletion, finding min/max) all have a logarithmic time complexity with respect to k.

Space Complexity: O(k) The space used is proportional to the size of the sliding window.

Code Examples

The code examples in Python, Java, C++, and Go provided in the original response demonstrate these approaches effectively. They are well-structured and include clear comments, making them easy to understand. The TypeScript example utilizes a custom Treap implementation for its multiset which has a higher constant factor but illustrates the same general algorithm as the other languages.

Choosing an Approach

Both approaches have the same asymptotic time complexity. The choice between them may depend on the specific constraints of the problem and personal preference. The dual-heap approach might offer slightly better performance in practice due to its generally simpler implementation, while the ordered sets approach might be easier to understand conceptually. For the purposes of the LeetCode question, either approach is appropriate.