# Sliding Window Median **Difficulty:** HARD [External](https://leetcode.com/problems/sliding-window-median) Canonical: https://scaleengineer.com/dsa/problems/sliding-window-median **Patterns:** [Sliding Window](https://scaleengineer.com/dsa/patterns/sliding-window) **Data structures:** Array, Hash Table, Heap (Priority Queue) **Companies:** [DoorDash](https://scaleengineer.com/companies/doordash), [Flipkart](https://scaleengineer.com/companies/flipkart), [Snowflake](https://scaleengineer.com/companies/snowflake), [Point72](https://scaleengineer.com/companies/point72), [Datadog](https://scaleengineer.com/companies/datadog) --- ## Problem 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` # Approaches ## Brute Force with Sorting 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. **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. **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. ### Explanation 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. ```java 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; } } ``` ### Algorithm 1. Initialize an empty list `medians` to store the results. 2. Iterate from `i = 0` to `n - k`, where `n` is the length of `nums`. This loop defines the start of each window. 3. For each `i`, create a temporary array (or list) containing elements from `nums[i]` to `nums[i + k - 1]`. 4. Sort this temporary array. 5. Calculate the median: - If `k` is odd, the median is the element at index `k / 2`. - If `k` is even, the median is the average of elements at indices `k / 2 - 1` and `k / 2`. 6. Add the calculated median to the `medians` list. 7. Return the `medians` list as an array. ## Two Heaps with Lazy Removal 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. **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. **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. ### Explanation 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. ```java 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 lower = new PriorityQueue<>(Collections.reverseOrder()); // min-heap for the larger half PriorityQueue higher = new PriorityQueue<>(); Map 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; } } ``` ### Algorithm 1. Initialize a max-heap (`lower`), a min-heap (`higher`), and a hash map (`toRemove`) for lazy removal. 2. Iterate through the `nums` array. For each element `nums[i]`: 3. **Add Element:** Add `nums[i]` to `lower`, then move `lower.poll()` to `higher`. This ensures elements in `higher` are always greater than or equal to elements in `lower`. 4. **Balance Sizes:** If `higher` has more elements than `lower`, move `higher.poll()` to `lower` to maintain the size invariant (`lower.size()` >= `higher.size()`). 5. **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 the `toRemove` map. b. **Rebalance After Pruning:** The heap sizes might have changed, so rebalance them again to ensure `lower.size()` is `k/2` or `(k+1)/2`. c. **Calculate Median:** The median is `lower.peek()` if `k` is odd, or `(lower.peek() + higher.peek()) / 2.0` if `k` is even. d. **Lazy Remove:** Mark the outgoing element `nums[i - k + 1]` for removal by adding it to the `toRemove` map. # Solutions ### Java ```java 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 ; } } ``` ### Python ```python ''' >>> 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]) >>> 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. ``` ### CPP ```cpp class Solution { public: vector medianSlidingWindow(vector &nums, int k) { vector res; multiset 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; } }; ```