Sliding Window Median
You're given an integer array nums and an integer k. A window covering k consecutive elements starts at the left end and moves right one position at a time, giving nums.length - k + 1 windows. Return the median of each window, in order, as a list of floats. The median is the middle value of the window once sorted, or the average of the two middle values when k is even. Values can repeat.
Examples
nums = [1,3,-1,-3,5,3,6,7], k = 3 returns [1.0,-1.0,-1.0,3.0,5.0,6.0]
The first window [1,3,-1] sorts to [-1,1,3], so its median is 1. The next window [3,-1,-3] sorts to [-3,-1,3], giving -1, and so on for all 6 windows.
nums = [1,2,3,4,2,3,1,4,2], k = 3 returns [2.0,3.0,3.0,3.0,2.0,3.0,2.0]
The 7 windows sort to [1,2,3], [2,3,4], [2,3,4], [2,3,4], [1,2,3], [1,3,4] and [1,2,4]. Each median is the middle of those three values.
nums = [1,2,3,4], k = 2 returns [1.5,2.5,3.5]
With an even k each window has two middle values, so the median is their average: (1 + 2) / 2, (2 + 3) / 2 and (3 + 4) / 2.
Constraints
- 1 <= k <= nums.length <= 10^5
Hints
You need the middle of a window that's constantly gaining and losing elements, how do you make both updates fast?
Two heaps with lazy deletion (or a TreeMap), balanced after each insertion and removal.
Maintain a max-heap (lower half) and min-heap (upper half). When the window shifts, insert the new element into the appropriate heap and mark the outgoing element as removed in a counter, lazily popping when it appears on top. After balancing, read the median from the heap tops based on whether k is odd or even.
Drill This: Your Approach First
Approach
Split the current window into a lower half and an upper half, with lower holding the same count or one more, so the median is lower's largest value (odd k) or the average of lower's largest and upper's smallest (even k). Each step, add the new value to the correct half, remove the value leaving the window, and move one value across if the sizes drift. Java keeps each half as a sorted map of value counts, which stays at O(n log k). Python uses two heaps of (value, index) pairs and drops an entry once its index has left the window and it reaches a top, so stale entries can pile up to O(n).
Time
O(n log n)
Space
O(n)
Pitfall
Solutions
class Solution {
public double[] medianSlidingWindow(int[] nums, int k) {
TreeMap<Integer, Integer> lower = new TreeMap<>(Collections.reverseOrder());
TreeMap<Integer, Integer> upper = new TreeMap<>();
int lowerSize = 0, upperSize = 0;
double[] result = new double[nums.length - k + 1];
for (int i = 0; i < nums.length; i++) {
int num = nums[i];
if (lowerSize == 0 || num <= lower.firstKey()) {
lower.merge(num, 1, Integer::sum);
lowerSize++;
} else {
upper.merge(num, 1, Integer::sum);
upperSize++;
}
if (i >= k) {
int out = nums[i - k];
if (lower.containsKey(out)) {
if (lower.get(out) == 1) lower.remove(out);
else lower.put(out, lower.get(out) - 1);
lowerSize--;
} else {
if (upper.get(out) == 1) upper.remove(out);
else upper.put(out, upper.get(out) - 1);
upperSize--;
}
}
// rebalance
while (lowerSize > upperSize + 1) {
int v = lower.firstKey();
if (lower.get(v) == 1) lower.remove(v);
else lower.put(v, lower.get(v) - 1);
upper.merge(v, 1, Integer::sum);
lowerSize--;
upperSize++;
}
while (upperSize > lowerSize) {
int v = upper.firstKey();
if (upper.get(v) == 1) upper.remove(v);
else upper.put(v, upper.get(v) - 1);
lower.merge(v, 1, Integer::sum);
upperSize--;
lowerSize++;
}
if (i >= k - 1) {
if (k % 2 == 1) result[i - k + 1] = lower.firstKey();
else result[i - k + 1] = ((double) lower.firstKey() + upper.firstKey()) / 2.0;
}
}
return result;
}
}import heapq
class Solution:
def medianSlidingWindow(self, nums, k: int):
# Heaps hold (value, index) so a duplicate value can't be confused with
# its twin in the other heap. Entries whose index has left the window
# are dropped lazily, when they surface at a top.
lower, upper = [], [] # lower is a max-heap via negated values
in_lower = [False] * len(nums)
lo_size = up_size = 0 # live entries only
result = []
def prune(i):
while lower and lower[0][1] <= i - k:
heapq.heappop(lower)
while upper and upper[0][1] <= i - k:
heapq.heappop(upper)
for i, num in enumerate(nums):
if i >= k:
if in_lower[i - k]:
lo_size -= 1
else:
up_size -= 1
prune(i)
if not lower or num <= -lower[0][0]:
heapq.heappush(lower, (-num, i))
in_lower[i] = True
lo_size += 1
else:
heapq.heappush(upper, (num, i))
up_size += 1
while lo_size > up_size + 1:
prune(i)
v, j = heapq.heappop(lower)
heapq.heappush(upper, (-v, j))
in_lower[j] = False
lo_size -= 1
up_size += 1
while up_size > lo_size:
prune(i)
v, j = heapq.heappop(upper)
heapq.heappush(lower, (-v, j))
in_lower[j] = True
up_size -= 1
lo_size += 1
if i >= k - 1:
prune(i)
if k % 2 == 1:
result.append(float(-lower[0][0]))
else:
result.append((-lower[0][0] + upper[0][0]) / 2.0)
return result