Sliding Window Median
HardPrompt
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] 6Example 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
Approaches
2 approaches with complexity analysis and trade-offs.
The most straightforward approach is to consider each sliding window independently. For every window, we can extract the k elements, put them into a temporary array, sort this array, and then find the median based on the sorted elements. This method is easy to understand but not performant.
Algorithm
- Initialize an empty list
mediansto store the results. - Iterate from
i = 0ton - k, wherenis the length ofnums. This loop defines the start of each window. - For each
i, create a temporary array (or list) containing elements fromnums[i]tonums[i + k - 1]. - Sort this temporary array.
- Calculate the median:
- If
kis odd, the median is the element at indexk / 2. - If
kis even, the median is the average of elements at indicesk / 2 - 1andk / 2.
- If
- Add the calculated median to the
medianslist. - Return the
medianslist as an array.
Walkthrough
This method iterates through all possible windows of size k. For each window, it creates a copy of the k elements. This temporary array is then sorted using a standard sorting algorithm. Once sorted, the median can be easily found by accessing the middle element(s). If k is odd, the median is the element at index k/2. If k is even, it's the average of the elements at k/2 - 1 and k/2. This process is repeated for all n - k + 1 windows.
import java.util.Arrays; class Solution { public double[] medianSlidingWindow(int[] nums, int k) { int n = nums.length; if (n == 0) { return new double[0]; } double[] medians = new double[n - k + 1]; for (int i = 0; i <= n - k; i++) { // Create a window of size k int[] window = new int[k]; for (int j = 0; j < k; j++) { window[j] = nums[i + j]; } // Sort the window Arrays.sort(window); // Calculate the median if (k % 2 != 0) { medians[i] = (double) window[k / 2]; } else { // Use long to prevent overflow before division double median = ((long) window[k / 2 - 1] + (long) window[k / 2]) / 2.0; medians[i] = median; } } return medians; }}Complexity
Time
O((n - k) * k log k) or simply O(n * k log k) - There are `n - k + 1` windows. For each window, we sort `k` elements, which takes `O(k log k)` time.
Space
O(k) - We use an auxiliary array of size `k` to store the elements of each window for sorting.
Trade-offs
Pros
Simple to understand and implement.
Requires minimal complex data structures.
Cons
Highly inefficient for large inputs due to repeated sorting.
It recomputes the entire sorted order for each window, even though consecutive windows overlap significantly.
A more efficient approach uses two heaps to maintain the two halves of the elements in the current window. A max-heap stores the smaller half, and a min-heap stores the larger half. This structure allows for finding the median in O(1) time (from the heap tops). To handle the sliding window efficiently, we add the new element and use a "lazy removal" technique for the outgoing element, avoiding a costly O(k) search-and-remove operation.
Algorithm
- Initialize a max-heap (
lower), a min-heap (higher), and a hash map (toRemove) for lazy removal. - Iterate through the
numsarray. For each elementnums[i]: - Add Element: Add
nums[i]tolower, then movelower.poll()tohigher. This ensures elements inhigherare always greater than or equal to elements inlower. - Balance Sizes: If
higherhas more elements thanlower, movehigher.poll()tolowerto maintain the size invariant (lower.size()>=higher.size()). - Process Window: If the window is full (
i >= k - 1): a. Prune Heaps: Remove invalid elements from the tops of the heaps by checking against thetoRemovemap. b. Rebalance After Pruning: The heap sizes might have changed, so rebalance them again to ensurelower.size()isk/2or(k+1)/2. c. Calculate Median: The median islower.peek()ifkis odd, or(lower.peek() + higher.peek()) / 2.0ifkis even. d. Lazy Remove: Mark the outgoing elementnums[i - k + 1]for removal by adding it to thetoRemovemap.
Walkthrough
We use a max-heap (lower) for the smaller half of numbers and a min-heap (higher) for the larger half. The heaps are balanced such that lower.size() is either equal to or one greater than higher.size(). This allows for constant-time median retrieval.
The main challenge is efficiently updating the heaps as the window slides. A naive removal from a heap takes O(k). To achieve O(log k) complexity per step, we use lazy removal. Instead of immediately removing an element when it leaves the window, we add it to a hash map (toRemove). When we need to access the top of a heap (for median calculation or balancing), we first check if it's in toRemove. If it is, we pop it from the heap and decrement its count in the map. We repeat this until the heap's top is a valid, current element.
import java.util.Collections;import java.util.HashMap;import java.util.Map;import java.util.PriorityQueue; class Solution { public double[] medianSlidingWindow(int[] nums, int k) { double[] result = new double[nums.length - k + 1]; // max-heap for the smaller half PriorityQueue<Integer> lower = new PriorityQueue<>(Collections.reverseOrder()); // min-heap for the larger half PriorityQueue<Integer> higher = new PriorityQueue<>(); Map<Integer, Integer> toRemove = new HashMap<>(); for (int i = 0; i < nums.length; i++) { // 1. Add the new element lower.add(nums[i]); higher.add(lower.poll()); // 2. Balance sizes if (higher.size() > lower.size()) { lower.add(higher.poll()); } // 3. If window is full, calculate median and prepare for next slide if (i >= k - 1) { // 3a. Prune invalid elements from heap tops while (!lower.isEmpty() && toRemove.getOrDefault(lower.peek(), 0) > 0) { toRemove.compute(lower.peek(), (key, val) -> val - 1); lower.poll(); } while (!higher.isEmpty() && toRemove.getOrDefault(higher.peek(), 0) > 0) { toRemove.compute(higher.peek(), (key, val) -> val - 1); higher.poll(); } // 3b. Rebalance after pruning if (higher.size() > lower.size()) { lower.add(higher.poll()); } if (lower.size() > higher.size() + 1) { higher.add(lower.poll()); } // 3c. Calculate median if (k % 2 == 1) { result[i - k + 1] = (double) lower.peek(); } else { result[i - k + 1] = ((long) lower.peek() + (long) higher.peek()) / 2.0; } // 3d. Mark outgoing element for removal int outNum = nums[i - k + 1]; toRemove.put(outNum, toRemove.getOrDefault(outNum, 0) + 1); } } return result; }}Complexity
Time
O(n log k) - For each of the `n` elements, we perform a constant number of heap operations (add, poll), each taking `O(log k)` time. Hash map operations are `O(1)` on average. The pruning process is amortized, as each element is added and removed from the heaps at most once.
Space
O(k) - The two heaps store `k` elements in total. The hash map for lazy removal can store up to `k` distinct elements in the worst case.
Trade-offs
Pros
Significantly more efficient than brute-force, making it suitable for large inputs.
It's a standard and powerful technique for dynamic median problems.
Cons
More complex to implement correctly compared to the brute-force method.
The logic for balancing, pruning, and lazy removal requires careful handling to avoid bugs.
Solutions
Solution
class MedianFinder { private PriorityQueue < Integer > small = new PriorityQueue <>( Comparator . reverseOrder ()); private PriorityQueue < Integer > large = new PriorityQueue <>(); private Map < Integer , Integer > delayed = new HashMap <>(); private int smallSize ; private int largeSize ; private int k ; public MedianFinder ( int k ) { this . k = k ; } public void addNum ( int num ) { if ( small . isEmpty () || num <= small . peek ()) { small . offer ( num ); ++ smallSize ; } else { large . offer ( num ); ++ largeSize ; } rebalance (); } public double findMedian () { return ( k & 1 ) == 1 ? small . peek () : (( double ) small . peek () + large . peek ()) / 2 ; } public void removeNum ( int num ) { delayed . merge ( num , 1 , Integer: : sum ); if ( num <= small . peek ()) { -- smallSize ; if ( num == small . peek ()) { prune ( small ); } } else { -- largeSize ; if ( num == large . peek ()) { prune ( large ); } } rebalance (); } private void prune ( PriorityQueue < Integer > pq ) { while (! pq . isEmpty () && delayed . containsKey ( pq . peek ())) { if ( delayed . merge ( pq . peek (), - 1 , Integer: : sum ) == 0 ) { delayed . remove ( pq . peek ()); } pq . poll (); } } private void rebalance () { if ( smallSize > largeSize + 1 ) { large . offer ( small . poll ()); -- smallSize ; ++ largeSize ; prune ( small ); } else if ( smallSize < largeSize ) { small . offer ( large . poll ()); -- largeSize ; ++ smallSize ; prune ( large ); } } } class Solution { public double [] medianSlidingWindow ( int [] nums , int k ) { MedianFinder finder = new MedianFinder ( k ); for ( int i = 0 ; i < k ; ++ i ) { finder . addNum ( nums [ i ]); } int n = nums . length ; double [] ans = new double [ n - k + 1 ]; ans [ 0 ] = finder . findMedian (); for ( int i = k ; i < n ; ++ i ) { finder . addNum ( nums [ i ]); finder . removeNum ( nums [ i - k ]); ans [ i - k + 1 ] = finder . findMedian (); } return ans ; } }''' >>> nums = [1,3,-1,-3,5,3,6,7] >>> k = 3 >>> window = sorted(nums[:k]) >>> window [-1, 1, 3] >>> >>> nums[k:] + [0] [-3, 5, 3, 6, 7, 0] >>> zip(nums, nums[k:] + [0]) <zip object at 0x108f384c0> >>> list(zip(nums, nums[k:] + [0])) [(1, -3), (3, 5), (-1, 3), (-3, 6), (5, 7), (3, 0)] >>> >>> >>> window.remove(1) >>> window [-1, 3] >>> bisect.insort(window, -3) >>> window [-3, -1, 3] ''' ''' >>> nums [1, 3, -1, -3, 5, 3, 6, 7] >>> >>> nums[1] 3 >>> nums[~1] 6 ''' import bisect class Solution ( object ): def medianSlidingWindow ( self , nums , k ): # this solution is just the natural flow window = sorted ( nums [: k ]) medians = [] for a , b in zip ( nums , nums [ k :] + [ 0 ]): # +[0] to keep the loop running # e.g. k=3 and nums[1,2,3], so it should enter the loop for one time medians . append (( window [ k // 2 ] + window [ ~ ( k // 2 )]) / 2. ) window . remove ( a ) bisect . insort ( window , b ) return medians ########### # heap solution # Since we are using k-size heap here, the time complexity is O(nlogk) # and space complexity is O(logk). def medianSlidingWindow ( nums , k ): small , large = [], [] for i , x in enumerate ( nums [: k ]): heapq . heappush ( small , ( - x , i )) for _ in range ( k - ( k >> 1 )): move ( small , large ) ans = [ get_med ( small , large , k )] for i , x in enumerate ( nums [ k :]): if x >= large [ 0 ][ 0 ]: heapq . heappush ( large , ( x , i + k )) if nums [ i ] <= large [ 0 ][ 0 ]: move ( large , small ) else : heapq . heappush ( small , ( - x , i + k )) if nums [ i ] >= large [ 0 ][ 0 ]: move ( small , large ) while small and small [ 0 ][ 1 ] <= i : heapq . heappop ( small ) while large and large [ 0 ][ 1 ] <= i : heapq . heappop ( large ) ans . append ( get_med ( small , large , k )) return ans def move ( h1 , h2 ): x , i = heapq . heappop ( h1 ) heapq . heappush ( h2 , ( - x , i )) def get_med ( h1 , h2 , k ): return h2 [ 0 ][ 0 ] * 1. if k & 1 else ( h2 [ 0 ][ 0 ] - h1 [ 0 ][ 0 ]) / 2.class Solution {public: vector<double> medianSlidingWindow(vector<int> &nums, int k) { vector<double> res; multiset<int> small, large; for (int i = 0; i < nums.size(); ++i) { if (i >= k) { if (small.count(nums[i - k])) small.erase(small.find(nums[i - k])); else if (large.count(nums[i - k])) large.erase(large.find(nums[i - k])); } if (small.size() <= large.size()) { if (large.empty() || nums[i] <= *large.begin()) small.insert(nums[i]); else { small.insert(*large.begin()); large.erase(large.begin()); large.insert(nums[i]); } } else { if (nums[i] >= *small.rbegin()) large.insert(nums[i]); else { large.insert(*small.rbegin()); small.erase(--small.end()); small.insert(nums[i]); } } if (i >= (k - 1)) { if (k % 2) res.push_back(*small.rbegin()); else res.push_back(((double)*small.rbegin() + *large.begin()) / 2); } } return res; }};Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.