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.
arr = [2,3,4], the median is 3.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 - 1Problem Overview: You are given an integer array and a window size k. As the window slides one step to the right, compute the median of the current window. The challenge is maintaining the median efficiently while elements enter and leave the window.
Approach 1: Brute Force (O(n * k log k) time, O(k) space)
The most direct approach recomputes the median for every window. Extract the k elements in the current window, sort them, and read the middle element (or the average of two middle elements for even k). Sorting costs O(k log k) per window and there are about n - k + 1 windows, resulting in O(n * k log k) time. Space complexity is O(k) to hold the temporary window. This approach is easy to implement and useful for verifying correctness, but it becomes slow when k grows large.
Approach 2: Dual Heap Approach (O(n log k) time, O(k) space)
This is the standard optimal solution. Maintain two heaps: a max heap for the smaller half of numbers and a min heap for the larger half. The heaps stay balanced so their sizes differ by at most one, allowing the median to be read directly from the heap tops. When the window slides, insert the new element and lazily remove the outgoing element using a hash map to track delayed deletions. Each insertion or removal costs O(log k), so processing all elements takes O(n log k) time. This technique combines heap (priority queue) operations with a small hash table for efficient cleanup.
Approach 3: Heap-Based Sliding Window with Lazy Deletion (O(n log k) time, O(k) space)
A variation of the dual heap approach explicitly focuses on lazy deletion. Instead of removing elements immediately when they fall out of the window, mark them in a map and clean them only when they appear at the top of a heap. This avoids expensive arbitrary deletions from a heap. The heaps maintain balance as elements are inserted and invalid ones are popped. Median lookup remains O(1). This method is widely used in competitive programming for sliding window median problems.
Approach 4: Multiset and Iterator (O(n log k) time, O(k) space)
Languages with ordered containers (like multiset in C++ or TreeSet-like structures) allow a different strategy. Store the current window in a balanced binary search tree and maintain an iterator pointing to the median element. When the window moves, insert the incoming value and erase the outgoing one while adjusting the iterator accordingly. Both operations take O(log k). Accessing the median becomes constant time. This approach is clean and deterministic but relies on ordered-set support.
Recommended for interviews: The dual heap approach is what most interviewers expect. It demonstrates understanding of heap balancing, lazy deletion, and sliding window optimization. Showing the brute force first proves you understand the problem, but implementing the O(n log k) heap solution demonstrates strong data structure skills.
The dual heap approach uses two heaps to maintain the sliding window median. The idea is to maintain a max heap for the left half of the data and a min heap for the right half. This allows for efficient retrieval of the median at any point:
This Python solution uses the `SortedList` from the `sortedcontainers` module to maintain an ordered list of numbers in the current window. As the window slides:
Python
Time Complexity: O(n log k), where n is the number of elements in nums and k is the window size because insertion and deletion in a SortedList take O(log k) time.
Space Complexity: O(k) because we store at most k elements in the SortedList.
This approach iteratively computes the median for each possible window by sorting the window at each step. This is a simpler approach but less efficient:
This straightforward Python solution sorts each subarray individually to determine the median. The simplicity comes at the cost of performance for larger datasets:
Python
Time Complexity: O(nk log k) due to sorting each subarray of size k for every possible window.
Space Complexity: O(k) to store the current window’s elements temporarily.
Use two heaps: a max-heap to keep track of the lower half of the window and a min-heap for the upper half. The max-heap stores the smaller half of numbers, while the min-heap stores the larger half. By maintaining the size property (balance) of these heaps, we can always pull the median based on the size of the window:
Efficient insertion and removal using heaps make this approach suitable for large inputs.
This solution defines three core functions: add_number to handle numbers entering the heap, remove_number deals with numbers leaving the heap, and balance_heaps keeps the two heaps balanced. The median is calculated based on the sizes of the heaps after adjusting them.
Time Complexity: O(n * log k), due to heap operations per window.
Space Complexity: O(k), for storing elements in the heaps.
Using a balanced binary search tree structure (like C++ STL's multiset) that maintains order can help efficiently find medians. This approach utilizes iterators, which allow seamless tracking of median positions as we move the sliding window:
This Java implementation utilizes a TreeMap to store the elements of the current window. Functions to add and remove elements adjust the frequency count within the set, allowing us to maintain window data. getMedian then determines the median based on the current state of the window.
Time Complexity: O(n * log k), due to tree operations within each window adjustment.
Space Complexity: O(k), for tracking window elements within the tree.
We can use two priority queues (min-heap and max-heap) to maintain the elements in the current window. One priority queue stores the smaller half of the elements, and the other priority queue stores the larger half of the elements. This way, the median of the current window is either the average of the top elements of the two heaps or one of the top elements.
We design a class MedianFinder to maintain the elements in the current window. This class includes the following methods:
add_num(num): Adds num to the current window.find_median(): Returns the median of the elements in the current window.remove_num(num): Removes num from the current window.prune(pq): If the top element of the heap is in the lazy deletion dictionary delayed, it pops the top element from the heap and decrements its lazy deletion count. If the lazy deletion count of the element becomes zero, it removes the element from the lazy deletion dictionary.rebalance(): If the number of elements in the smaller half exceeds the number of elements in the larger half by 2, it moves the top element of the larger half to the smaller half. If the number of elements in the smaller half is less than the number of elements in the larger half, it moves the top element of the larger half to the smaller half.In the add_num(num) method, we first consider adding num to the smaller half. If num is greater than the top element of the larger half, we add num to the larger half. Then we call the rebalance() method to ensure that the size difference between the two priority queues does not exceed 1.
In the remove_num(num) method, we increment the lazy deletion count of num. Then we compare num with the top element of the smaller half. If num is less than or equal to the top element of the smaller half, we update the size of the smaller half and call the prune() method to ensure that the top element of the smaller half is not in the lazy deletion dictionary. Otherwise, we update the size of the larger half and call the prune() method to ensure that the top element of the larger half is not in the lazy deletion dictionary.
In the find_median() method, if the current window size is odd, we return the top element of the smaller half; otherwise, we return the average of the top elements of the smaller half and the larger half.
In the prune(pq) method, if the top element of the heap is in the lazy deletion dictionary, it pops the top element from the heap and decrements its lazy deletion count. If the lazy deletion count of the element becomes zero, it removes the element from the lazy deletion dictionary.
In the rebalance() method, if the number of elements in the smaller half exceeds the number of elements in the larger half by 2, it moves the top element of the larger half to the smaller half. If the number of elements in the smaller half is less than the number of elements in the larger half, it moves the top element of the larger half to the smaller half.
The time complexity is O(n times log n), and the space complexity is O(n). Here, n is the length of the array nums.
We can use two ordered sets to maintain the elements in the current window. The ordered set l stores the smaller half of the elements in the current window, and the ordered set r stores the larger half of the elements.
We traverse the array nums. For each element x, we add it to the ordered set r, then move the smallest element in the ordered set r to the ordered set l. If the size of the ordered set l is greater than the size of the ordered set r by more than 1, we move the largest element in the ordered set l to the ordered set r.
If the total number of elements in the current window is k and the size is odd, the maximum value in the ordered set l is the median. If the size of the current window is even, the average of the maximum value in the ordered set l and the minimum value in the ordered set r is the median. Then, we remove the leftmost element of the window and continue traversing the array.
The time complexity is O(n log k), and the space complexity is O(k). Here, n is the length of the array nums.
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Dual Heap Approach | Time Complexity: O(n log k), where n is the number of elements in nums and k is the window size because insertion and deletion in a SortedList take O(log k) time. Space Complexity: O(k) because we store at most k elements in the SortedList. |
| Brute Force Approach | Time Complexity: O(nk log k) due to sorting each subarray of size k for every possible window. Space Complexity: O(k) to store the current window’s elements temporarily. |
| Heap-Based Approach | Time Complexity: O(n * log k), due to heap operations per window. Space Complexity: O(k), for storing elements in the heaps. |
| Multiset and Iterator Approach | Time Complexity: O(n * log k), due to tree operations within each window adjustment. Space Complexity: O(k), for tracking window elements within the tree. |
| Dual Priority Queues (Min-Heap and Max-Heap) + Lazy Deletion | — |
| Ordered Set | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Sorting | O(n * k log k) | O(k) | Small window sizes or quick correctness check |
| Dual Heap (Max Heap + Min Heap) | O(n log k) | O(k) | General optimal solution for interviews and production |
| Heap with Lazy Deletion | O(n log k) | O(k) | When implementing sliding window medians efficiently with priority queues |
| Multiset / Balanced BST | O(n log k) | O(k) | Languages with ordered sets like C++ or Java Tree structures |
LeetCode - Sliding Window Median (480) • LeetCode Learning • 19,856 views views
Watch 9 more video solutions →Practice Sliding Window Median with our built-in code editor and test cases.
Practice on FleetCode