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 - 1The key challenge in Sliding Window Median is efficiently maintaining the median as the window moves across the array. Since elements continuously enter and leave the window, recalculating the median from scratch each time would be too slow.
A common approach uses two heaps: a max-heap for the smaller half of numbers and a min-heap for the larger half. This structure allows quick access to the median while keeping both halves balanced. As the window slides, new elements are inserted into the appropriate heap and outdated elements must be removed. Because direct deletion from heaps is expensive, many solutions use lazy deletion with a hash map to mark elements that should be ignored when they reach the top.
The heaps are rebalanced so their sizes differ by at most one, allowing easy median extraction. This approach processes each element efficiently, leading to an overall time complexity of O(n log k) for window size k, with O(k) extra space.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Two Heaps with Lazy Deletion | O(n log k) | O(k) |
| Balanced BST / Multiset | O(n log k) | O(k) |
NeetCode
Use these hints if you're stuck. Try solving on your own first.
The simplest of solutions comes from the basic idea of finding the median given a set of numbers. We know that by definition, a median is the center element (or an average of the two center elements). Given an unsorted list of numbers, how do we find the median element? If you know the answer to this question, can we extend this idea to every sliding window that we come across in the array?
Is there a better way to do what we are doing in the above hint? Don't you think there is duplication of calculation being done there? Is there some sort of optimization that we can do to achieve the same result? This approach is merely a modification of the basic approach except that it simply reduces duplication of calculations once done.
The third line of thought is also based on this same idea but achieving the result in a different way. We obviously need the window to be sorted for us to be able to find the median. Is there a data-structure out there that we can use (in one or more quantities) to obtain the median element extremely fast, say O(1) time while having the ability to perform the other operations fairly efficiently as well?
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:
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.
1from sortedcontainers import SortedList
2
3class Solution:
4 def medianSlidingWindow(self, nums, k):
5 window = SortedList()
6 medians = []
7 for i, num in enumerate(nums):
8 window.add(num)
9 if len(window) > k:
10 window.remove(nums[i-k])
11 if len(window) == k:
12 if k % 2 == 0:
13 medians.append((window[k//2-1] + window[k//2]) / 2)
14 else:
15 medians.append(window[k//2])
16 return medians
17This Python solution uses the `SortedList` from the `sortedcontainers` module to maintain an ordered list of numbers in the current window. As the window slides:
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:
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.
1class Solution:
2 def medianSlidingWindow(self, nums, k):
3Use 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.
Time Complexity: O(n * log k), due to heap operations per window.
Space Complexity: O(k), for storing elements in the heaps.
1from heapq import heappush, heappop
2
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:
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.
1import java.util.*;
2
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, Sliding Window Median is considered a hard interview problem and has appeared in interviews at large tech companies. It tests knowledge of heaps, sliding window techniques, and careful data structure management.
Removing arbitrary elements directly from a heap is inefficient. Lazy deletion marks elements for removal in a hash map and only deletes them when they appear at the top of the heap, keeping operations efficient.
Heaps (priority queues) are typically the best choice because they allow quick access to the largest and smallest elements of each half. Some implementations also use balanced binary search trees or multisets to maintain sorted order within the window.
The most common optimal approach uses two heaps: a max-heap for the lower half of elements and a min-heap for the upper half. Combined with lazy deletion using a hash map, this allows efficient insertion, removal, and median retrieval while the window slides.
This straightforward Python solution sorts each subarray individually to determine the median. The simplicity comes at the cost of performance for larger datasets:
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.
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.