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.
1#include <vector>
2#include <queue>
3#include <iostream>
std::vector<double> medianSlidingWindow(std::vector<int>& nums, int k) {
std::priority_queue<int> max_heap;
std::priority_queue<int, std::vector<int>, std::greater<int>> min_heap;
std::vector<double> medians;
auto add_number = [&](int number) {
if (max_heap.empty() || number <= max_heap.top())
max_heap.push(number);
else
min_heap.push(number);
balance_heaps();
};
auto remove_number = [&](int number) {
if (number <= max_heap.top()) {
max_heap.push(INT_MIN); // Add a small number to force closure
max_heap.pop();
} else {
min_heap.push(INT_MAX); // Add a large number to force closure
min_heap.pop();
}
balance_heaps();
};
auto balance_heaps = [&]() {
if (max_heap.size() > min_heap.size() + 1) {
min_heap.push(max_heap.top());
max_heap.pop();
} else if (min_heap.size() > max_heap.size()) {
max_heap.push(min_heap.top());
min_heap.pop();
}
};
for (int i = 0; i < nums.size(); i++) {
add_number(nums[i]);
if (i >= k - 1) {
if (max_heap.size() > min_heap.size())
medians.push_back(max_heap.top());
else
medians.push_back((max_heap.top() + min_heap.top()) / 2.0);
remove_number(nums[i - k + 1]);
}
}
return medians;
}
int main() {
std::vector<int> nums = {1, 3, -1, -3, 5, 3, 6, 7};
int k = 3;
std::vector<double> results = medianSlidingWindow(nums, k);
for (double result : results) {
std::cout << result << " " << std::endl;
}
return 0;
}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.
1using System;
2using System.Collections.Generic;
3using System.Linq;
4
public class Solution {
public double[] MedianSlidingWindow(int[] nums, int k) {
SortedDictionary<int, int> window = new SortedDictionary<int, int>();
double[] medians = new double[nums.Length - k + 1];
int left = 0, right = 0;
void AddNumber(int num) {
if (window.ContainsKey(num))
window[num]++;
else
window[num] = 1;
}
void RemoveNumber(int num) {
if (window[num] == 1)
window.Remove(num);
else
window[num]--;
}
double GetMedian() {
int count = 0;
int midpoint = (k + 1) / 2;
int? lower = null, upper = null;
foreach (var entry in window) {
count += entry.Value;
if (!lower.HasValue && count >= midpoint) {
lower = entry.Key;
}
if (count >= (midpoint + k % 2) / 2) {
upper = entry.Key;
break;
}
}
return (lower.Value + upper.Value) / 2.0;
}
while (right < k) {
AddNumber(nums[right++]);
}
right--; // Adjust to last element in window
for (; right < nums.Length; right++) {
if (right >= k) {
medians[left] = GetMedian();
RemoveNumber(nums[left]);
left++;
}
if (right + 1 < nums.Length) {
AddNumber(nums[right + 1]);
}
}
medians[left] = GetMedian();
return medians;
}
public static void Main() {
int[] nums = {1, 3, -1, -3, 5, 3, 6, 7};
int k = 3;
var sol = new Solution();
var medians = sol.MedianSlidingWindow(nums, k);
Console.WriteLine(string.Join(", ", medians));
}
}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:
The C++ solution makes use of two priority queues to maintain two parts of the sliding window. The add_number and remove_number functions are responsible for heap changes, followed by balance_heaps to ensure the heap sizes remain appropriate.
The C# implementation uses a sorted dictionary to manage the counts and order of numbers in the window. Add and remove operations modify this dictionary. The GetMedian function determines the median based on the set order and current window size, iterating over sorted keys to reach the median position.