Sliding Window Median
Problem Description
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 is3. - 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
Solve it on LeetCode
Approaches
1. Brute Force Using Sorting
Intuition:
The brute force approach involves recalculating the median every time the sliding window moves. For each new window, we sort the window elements and directly compute the median. This approach is straightforward but inefficient, as sorting each time takes considerable time.
Steps:
- Iterate through the
numsarray, from the start to the end minus the window sizek. - For each position, get the subarray of size
kand sort it. - Calculate the median:
- If
kis odd, the median is the middle element of the sorted window. - If
kis even, the median is the average of the two middle elements. - Store the median in the result.
Code:
- Time Complexity: Sorting each window takes O(k logk), and there are (n-k+1) windows. Total time complexity is O((n-k+1) * k * logk).
- Space Complexity: O(k), as we store the subarray for sorting.
2. Maintaining Two Heaps (Optimal)
Intuition:
We can use two heaps to maintain the order of the sliding window:
- A max-heap to store the smaller half of the numbers.
- A min-heap to store the larger half of the numbers.
By always maintaining balance between the two heaps, the median can be derived efficiently:
- If k is odd, the max-heap will give the median.
- If k is even, the median is the average of the roots of both heaps.
Steps:
- Use a
PriorityQueuefor both heaps. - Process the elements of the array: add new numbers, remove the old numbers going out of the window.
- Ensure the balance between the two heaps every time a insertion or removal is done.
- Calculate the median using the top elements of the heaps.
Code:
- Time Complexity: Each operation of insertion/removal/balance takes O(log k). For each window, there are approximately constant number of operations. Overall time complexity is O(n log k).
- Space Complexity: O(k), space used by both heaps together.