Sliding Window Median
Description
The median of a list of numbers is its middle value once the list is sorted. If the list has an even number of values, there's no single middle value, and the median is the average of the two middle ones. So the median of [2, 3, 4] is 3, and the median of [1, 2, 3, 4] is (2 + 3) / 2 = 2.5.
You get an integer array nums and an integer k. A window of size k starts at the left end of the array and moves right one position at a time, so it always holds k consecutive values.
Return the median of each window, from left to right. Each median is printed with 5 decimal places, so 2.5 shows as 2.50000.
Examples
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: Each window holds 3 values, so its median is the middle one once sorted: [1, 3, -1] sorts to [-1, 1, 3] for 1, then -1, -1, 3, 5 and 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]
Explanation: Seven windows of 3 values: [3, 4, 2] sorts to [2, 3, 4] for 3, and [2, 3, 1] to [1, 2, 3] for 2.
Example 3
Input: nums = [5, 2, 8, 1, 9], k = 4
Output: [3.50000, 5.00000]
Explanation: An even window has two middle values, and the median is their average: [5, 2, 8, 1] sorts to [1, 2, 5, 8] for (2 + 5) / 2 = 3.5, and [2, 8, 1, 9] to [1, 2, 8, 9] for 5.
Constraints
- 1 ≤ k ≤ nums.length ≤ 10^5
- −2^31 ≤ nums[i] ≤ 2^31 − 1
Editorial
Brute Force
Intuition
Take each window, sort a copy of it, and read the middle. In the sorted copy the two middle positions are (k − 1) / 2 and k / 2, rounded down. When k is odd they're the same position, so averaging the values at both gives the median either way.
Step-by-Step Explanation
Let's trace nums = [1, 3, -1, -3, 5, 3, 6, 7], k = 3:
- Window
[1, 3, -1]sorts to[-1, 1, 3]: the median is1. - Window
[3, -1, -3]sorts to[-3, -1, 3]: the median is-1. - Window
[-1, -3, 5]sorts to[-3, -1, 5]: the median is-1. - Window
[-3, 5, 3]sorts to[-3, 3, 5]: the median is3. - Window
[5, 3, 6]sorts to[3, 5, 6]: the median is5. - Window
[3, 6, 7]sorts to[3, 6, 7]: the median is6.
Sort Every Window — The outlined window, and below it the same values sorted, with the middle in green.
Algorithm
- For each start
ifrom 0 ton − k: copynums[i .. i + k − 1]and sort the copy. - Its median is the average of the values at positions
(k − 1) / 2andk / 2. - Return the medians in order.
Code
C++ and Java turn one middle value into a double before adding: two ints near 2^31 overflow when added.
class Solution {
public:
vector<double> medianSlidingWindow(vector<int>& nums, int k) {
vector<double> out;
for (int i = 0; i + k <= (int)nums.size(); i++) {
vector<int> window(nums.begin() + i, nums.begin() + i + k); // a copy of this window
sort(window.begin(), window.end());
out.push_back(((double)window[(k - 1) / 2] + window[k / 2]) / 2); // one middle, or two averaged
}
return out;
}
};
class Solution:
def medianSlidingWindow(self, nums: List[int], k: int) -> List[float]:
out = []
for i in range(len(nums) - k + 1):
window = sorted(nums[i:i + k]) # a sorted copy of this window
out.append((window[(k - 1) // 2] + window[k // 2]) / 2) # one middle, or two averaged
return out
class Solution {
public double[] medianSlidingWindow(int[] nums, int k) {
double[] out = new double[nums.length - k + 1];
for (int i = 0; i + k <= nums.length; i++) {
int[] window = Arrays.copyOfRange(nums, i, i + k); // a copy of this window
Arrays.sort(window);
out[i] = ((double) window[(k - 1) / 2] + window[k / 2]) / 2; // one middle, or two averaged
}
return out;
}
}
var medianSlidingWindow = function(nums, k) {
const out = [];
for (let i = 0; i + k <= nums.length; i++) {
const window = nums.slice(i, i + k).sort((a, b) => a - b); // a sorted copy of this window
out.push((window[(k - 1) >> 1] + window[k >> 1]) / 2); // one middle, or two averaged
}
return out;
};
Complexity Analysis
Time Complexity: O((n − k + 1) · k log k)
Each of the n − k + 1 windows is sorted.
Space Complexity: O(k)
The sorted copy.
Why This Approach Is Not Efficient
Every window is sorted from scratch. On 10,000 random values in Python it took 105 ms with k = 100, 1,552 ms with k = 1,000 and 5,441 ms with k = 5,000. With 10^5 values and k = 5 × 10^4 it's tens of billions of steps, over the time limit in C++, Python, Java and JavaScript.
But two neighbouring windows share k − 1 values: a slide drops one value and adds one. So keep one sorted copy and update it, deleting the value that leaves and inserting the value that arrives. On the same values the updated copy took 8.8 ms, 12.7 ms and 16.8 ms.
Better Approach - Keep the Window Sorted
Intuition
Sort the first window once. For each slide, binary search finds the value that leaves, and it's deleted; binary search finds where the new value goes, and it's inserted there. The copy stays sorted, so the median is read from the middle as before.
Step-by-Step Explanation
Let's trace nums = [1, 3, -1, -3, 5, 3, 6, 7], k = 3:
- Sort the first window once:
[-1, 1, 3], median1. 1leaves from position 1 and-3goes in at position 0:[-3, -1, 3], median-1.3leaves from position 2 and5goes in at position 2:[-3, -1, 5], median-1.-1leaves from position 1 and3goes in at position 1:[-3, 3, 5], median3.-3leaves from position 0 and6goes in at position 2:[3, 5, 6], median5.5leaves from position 1 and7goes in at position 2:[3, 6, 7], median6.
One Sorted Window, Updated — The outlined window, and below it the one sorted copy: the value just inserted in indigo, the middle in green.
Algorithm
- Copy the first
kvalues and sort them. - Read the median from the middle.
- For each
ifromkton − 1: binary search fornums[i − k]and delete it, binary search for the place ofnums[i]and insert it, then read the median.
Code
Python's bisect module does the binary searches. Java keeps the window in an int array and moves values with System.arraycopy, and JavaScript does the same with an Int32Array and copyWithin.
class Solution {
public:
vector<double> medianSlidingWindow(vector<int>& nums, int k) {
vector<int> window(nums.begin(), nums.begin() + k);
sort(window.begin(), window.end()); // sorted once, then kept sorted
vector<double> out = {((double)window[(k - 1) / 2] + window[k / 2]) / 2};
for (int i = k; i < (int)nums.size(); i++) {
window.erase(lower_bound(window.begin(), window.end(), nums[i - k])); // the value leaving
window.insert(upper_bound(window.begin(), window.end(), nums[i]), nums[i]); // the value arriving
out.push_back(((double)window[(k - 1) / 2] + window[k / 2]) / 2);
}
return out;
}
};
from bisect import bisect_left, insort
class Solution:
def medianSlidingWindow(self, nums: List[int], k: int) -> List[float]:
window = sorted(nums[:k]) # sorted once, then kept sorted
out = [(window[(k - 1) // 2] + window[k // 2]) / 2]
for i in range(k, len(nums)):
window.pop(bisect_left(window, nums[i - k])) # the value leaving: find it, delete it
insort(window, nums[i]) # the value arriving: find its place, insert it
out.append((window[(k - 1) // 2] + window[k // 2]) / 2)
return out
class Solution {
public double[] medianSlidingWindow(int[] nums, int k) {
int[] window = Arrays.copyOf(nums, k);
Arrays.sort(window); // sorted once, then kept sorted
double[] out = new double[nums.length - k + 1];
out[0] = ((double) window[(k - 1) / 2] + window[k / 2]) / 2;
for (int i = k; i < nums.length; i++) {
int at = Arrays.binarySearch(window, 0, k, nums[i - k]); // the value leaving: find it,
System.arraycopy(window, at + 1, window, at, k - 1 - at); // and close the gap
int to = Arrays.binarySearch(window, 0, k - 1, nums[i]); // the value arriving: find its place,
if (to < 0) to = -to - 1;
System.arraycopy(window, to, window, to + 1, k - 1 - to); // and open a gap there
window[to] = nums[i];
out[i - k + 1] = ((double) window[(k - 1) / 2] + window[k / 2]) / 2;
}
return out;
}
}
var medianSlidingWindow = function(nums, k) {
const firstAtLeast = (a, n, x) => { // binary search in a[0 .. n - 1]: the first index with a value >= x
let lo = 0, hi = n;
while (lo < hi) {
const mid = (lo + hi) >> 1;
if (a[mid] < x) lo = mid + 1; else hi = mid;
}
return lo;
};
const window = Int32Array.from(nums.slice(0, k)).sort(); // sorted once, then kept sorted
const out = [(window[(k - 1) >> 1] + window[k >> 1]) / 2];
for (let i = k; i < nums.length; i++) {
const at = firstAtLeast(window, k, nums[i - k]); // the value leaving: find it,
window.copyWithin(at, at + 1); // and close the gap
const to = firstAtLeast(window, k - 1, nums[i]); // the value arriving: find its place,
window.copyWithin(to + 1, to, k - 1); // and open a gap there
window[to] = nums[i];
out.push((window[(k - 1) >> 1] + window[k >> 1]) / 2);
}
return out;
};
Complexity Analysis
Time Complexity: O(n · k)
Finding a position is O(log k), but deleting or inserting shifts up to k values. The shifts are fast block moves in memory.
Space Complexity: O(k)
The sorted window.
Why This Approach Is Not Efficient
It passes here, because the shifts are fast copies in memory. But each slide still moves up to k values. Timed in Python on 10^5 random values, it took 88.7 ms with k = 100, faster than the heaps below at 445 ms. With k = 10,000 it took 492 ms against 378 ms, and with k = 50,000, 1,595 ms against 274 ms: the shifts grow with k.
The median needs only two values from the window: the largest of its lower half and the smallest of its upper half. Two heaps facing each other keep both on top, and take a new value in O(log k). What they can't do cheaply is delete a value from the middle, and the window does that on every slide.
Optimal Approach - Two Heaps That Delete Late
Intuition
Keep the window's lower half in a max-heap and its upper half in a min-heap, the lower half holding the extra value when k is odd. The median is the lower half's top, or the average of the two tops.
A new value goes into the lower half if it's at most the lower half's top, and into the upper half otherwise. If the halves then differ by more than that one extra value, a top moves across.
The value that leaves is the hard part, since a heap can't delete from its middle cheaply. So don't: mark it in a count of deleted values and take it off its half's live count, but leave it in the heap. Its half is easy to tell: it's in the lower half if it's at most the lower half's top. It's popped only when it reaches a top, the one place where it could be read. After every move, clean the top it uncovered: pop marked values while one sits on top. Balance by the live counts, never the heaps' sizes.
Step-by-Step Explanation
Let's trace nums = [1, 3, -1, -3, 5, 3, 6, 7], k = 3:
- Add
[1, 3, -1]one at a time: the lower half's top is1, so the median is1. -3goes into the lower half; the lower half now has two more, so its top, 1, moves up.1leaves the upper half, popped at once. The median is-1.5goes into the upper half.3leaves the upper half, popped at once. The median is-1.3goes into the upper half.-1leaves the lower half, popped at once; the upper half now has more, so its top, 3, moves down. The median is3.6goes into the upper half.-3leaves the lower half, marked and left inside its heap; the upper half now has more, so its top, 5, moves down. The median is5.7goes into the upper half.5leaves the lower half, popped at once; the upper half now has more, so its top, 6, moves down. The median is6.
Two Halves, Deleting Late — The top row is both heaps' contents, the lower half then the upper half, with their tops marked and the median in green. A deleted value still inside a heap is dimmed. Below, the window.
Algorithm
- Keep
low, a max-heap, andhigh, a min-heap, a count of the values marked as deleted, and the number of live values in each half. - Add x: push it into
lowiflowis empty orxis at most its top, otherwise intohigh. Balance. - Remove x: mark it. If
xis at mostlow's top, count it out oflow, and if it'slow's top, cleanlow; otherwise do the same withhigh. Balance. - Balance: if
lowhas two more live values thanhigh, move its top tohighand cleanlow. Ifhighhas more live values thanlow, move its top tolowand cleanhigh. - Clean a heap: while its top is marked, pop it and unmark it once.
- Median:
low's top iflowhas more live values, otherwise the average of the two tops. - Add the first
kvalues and read the median; then for each next value, add it, remove the one leaving, and read the median.
Code
Java and C++ keep the marks in a hash map. JavaScript has no heap built in, so its version carries the MinHeap class from Introduction to Heaps, once with the comparison flipped. In C++, a multiset with an iterator kept on the median does the same job in O(log k) and deletes directly.
class Solution {
priority_queue<int> low; // the lower half, largest on top
priority_queue<int, vector<int>, greater<int>> high; // the upper half, smallest on top
unordered_map<int, int> gone; // deleted, but maybe still inside a heap
int nLow = 0, nHigh = 0; // live values in each half
template <class Heap> void clean(Heap& heap) { // drop deleted values sitting on top
while (!heap.empty() && gone[heap.top()] > 0) {
gone[heap.top()]--;
heap.pop();
}
}
void balance() { // the lower half holds the extra value, if any
if (nLow > nHigh + 1) {
high.push(low.top()); low.pop(); nLow--; nHigh++;
clean(low);
} else if (nHigh > nLow) {
low.push(high.top()); high.pop(); nLow++; nHigh--;
clean(high);
}
}
void add(int x) {
if (low.empty() || x <= low.top()) { low.push(x); nLow++; }
else { high.push(x); nHigh++; }
balance();
}
void remove(int x) {
gone[x]++; // mark it; it leaves the heap when it surfaces
if (x <= low.top()) {
nLow--;
if (x == low.top()) clean(low);
} else {
nHigh--;
if (x == high.top()) clean(high);
}
balance();
}
double median() { // a double before adding: two ints can overflow
return nLow > nHigh ? low.top() : ((double)low.top() + high.top()) / 2;
}
public:
vector<double> medianSlidingWindow(vector<int>& nums, int k) {
for (int i = 0; i < k; i++) add(nums[i]);
vector<double> out = {median()};
for (int i = k; i < (int)nums.size(); i++) {
add(nums[i]);
remove(nums[i - k]);
out.push_back(median());
}
return out;
}
};
import heapq
from collections import Counter
class DualHeap:
"""A running median that can delete: a deleted value stays in its heap until it reaches the top."""
def __init__(self):
self.low, self.high = [], [] # the lower half as negatives (a max-heap), the upper half
self.gone = Counter() # deleted, but maybe still inside a heap
self.n_low = self.n_high = 0 # live values in each half
def _clean(self, heap, sign): # drop deleted values sitting on top
while heap and self.gone[sign * heap[0]]:
self.gone[sign * heapq.heappop(heap)] -= 1
def _balance(self): # the lower half holds the extra value, if any
if self.n_low > self.n_high + 1:
heapq.heappush(self.high, -heapq.heappop(self.low))
self.n_low, self.n_high = self.n_low - 1, self.n_high + 1
self._clean(self.low, -1)
elif self.n_high > self.n_low:
heapq.heappush(self.low, -heapq.heappop(self.high))
self.n_low, self.n_high = self.n_low + 1, self.n_high - 1
self._clean(self.high, 1)
def add(self, x):
if not self.low or x <= -self.low[0]:
heapq.heappush(self.low, -x)
self.n_low += 1
else:
heapq.heappush(self.high, x)
self.n_high += 1
self._balance()
def remove(self, x):
self.gone[x] += 1 # mark it; it leaves the heap when it surfaces
if x <= -self.low[0]:
self.n_low -= 1
if x == -self.low[0]:
self._clean(self.low, -1)
else:
self.n_high -= 1
if x == self.high[0]:
self._clean(self.high, 1)
self._balance()
def median(self):
if self.n_low > self.n_high:
return float(-self.low[0])
return (-self.low[0] + self.high[0]) / 2
class Solution:
def medianSlidingWindow(self, nums: List[int], k: int) -> List[float]:
window = DualHeap()
for x in nums[:k]:
window.add(x)
out = [window.median()]
for i in range(k, len(nums)):
window.add(nums[i])
window.remove(nums[i - k])
out.append(window.median())
return out
class Solution {
private final PriorityQueue<Integer> low = new PriorityQueue<>(Collections.reverseOrder()); // largest on top
private final PriorityQueue<Integer> high = new PriorityQueue<>(); // smallest on top
private final Map<Integer, Integer> gone = new HashMap<>(); // deleted, but maybe still inside a heap
private int nLow, nHigh; // live values in each half
public double[] medianSlidingWindow(int[] nums, int k) {
for (int i = 0; i < k; i++) add(nums[i]);
double[] out = new double[nums.length - k + 1];
out[0] = median();
for (int i = k; i < nums.length; i++) {
add(nums[i]);
remove(nums[i - k]);
out[i - k + 1] = median();
}
return out;
}
private void clean(PriorityQueue<Integer> heap) { // drop deleted values sitting on top
while (!heap.isEmpty() && gone.getOrDefault(heap.peek(), 0) > 0) gone.merge(heap.poll(), -1, Integer::sum);
}
private void balance() { // the lower half holds the extra value, if any
if (nLow > nHigh + 1) {
high.offer(low.poll()); nLow--; nHigh++;
clean(low);
} else if (nHigh > nLow) {
low.offer(high.poll()); nLow++; nHigh--;
clean(high);
}
}
private void add(int x) {
if (low.isEmpty() || x <= low.peek()) { low.offer(x); nLow++; }
else { high.offer(x); nHigh++; }
balance();
}
private void remove(int x) {
gone.merge(x, 1, Integer::sum); // mark it; it leaves the heap when it surfaces
if (x <= low.peek()) {
nLow--;
if (x == low.peek()) clean(low);
} else {
nHigh--;
if (x == high.peek()) clean(high);
}
balance();
}
private double median() { // a double before adding: two ints can overflow
return nLow > nHigh ? low.peek() : ((double) low.peek() + high.peek()) / 2;
}
}
// A min-heap in an array: the children of i are at 2i + 1 and 2i + 2, its parent at (i - 1) >> 1.
// less(x, y) says x goes above y: smallest on top unless you pass another.
class MinHeap {
constructor(less = (x, y) => x < y) { this.a = []; this.less = less; }
push(x) {
const a = this.a;
a.push(x);
let i = a.length - 1;
while (i > 0 && this.less(a[i], a[(i - 1) >> 1])) { // sift up while the parent is bigger
const p = (i - 1) >> 1;
[a[i], a[p]] = [a[p], a[i]];
i = p;
}
}
pop() {
const a = this.a;
const top = a[0], last = a.pop();
if (a.length) {
a[0] = last; // the last value takes the root, then sifts down
let i = 0;
while (true) {
const l = 2 * i + 1, r = 2 * i + 2;
let m = i;
if (l < a.length && this.less(a[l], a[m])) m = l;
if (r < a.length && this.less(a[r], a[m])) m = r; // the smaller child, or the bigger ends up above it
if (m === i) break;
[a[i], a[m]] = [a[m], a[i]];
i = m;
}
}
return top;
}
}
var medianSlidingWindow = function(nums, k) {
const low = new MinHeap((x, y) => x > y); // the lower half, largest on top
const high = new MinHeap(); // the upper half, smallest on top
const gone = new Map(); // deleted, but maybe still inside a heap
let nLow = 0, nHigh = 0; // live values in each half
const clean = (heap) => { // drop deleted values sitting on top
while (heap.a.length && gone.get(heap.a[0]) > 0) {
const x = heap.pop();
gone.set(x, gone.get(x) - 1);
}
};
const balance = () => { // the lower half holds the extra value, if any
if (nLow > nHigh + 1) {
high.push(low.pop()); nLow--; nHigh++;
clean(low);
} else if (nHigh > nLow) {
low.push(high.pop()); nLow++; nHigh--;
clean(high);
}
};
const add = (x) => {
if (!low.a.length || x <= low.a[0]) { low.push(x); nLow++; }
else { high.push(x); nHigh++; }
balance();
};
const remove = (x) => {
gone.set(x, (gone.get(x) || 0) + 1); // mark it; it leaves the heap when it surfaces
if (x <= low.a[0]) {
nLow--;
if (x === low.a[0]) clean(low);
} else {
nHigh--;
if (x === high.a[0]) clean(high);
}
balance();
};
const median = () => nLow > nHigh ? low.a[0] : (low.a[0] + high.a[0]) / 2;
for (let i = 0; i < k; i++) add(nums[i]);
const out = [median()];
for (let i = k; i < nums.length; i++) {
add(nums[i]);
remove(nums[i - k]);
out.push(median());
}
return out;
};
Complexity Analysis
Time Complexity: O(n log n)
Each value is pushed once and popped at most once, and each add or remove moves at most one top across. A marked value can wait inside a heap, so a heap can hold more than k entries, up to n.
Space Complexity: O(n)
The heaps and the marks, when marked values pile up below the tops.
Common Mistakes
Each of these looks right on a quick read, and the tests still reject it. The outputs below come from running the code.
Flooring the average. (window[(k - 1) // 2] + window[k // 2]) // 2
On nums = [1, 2], k = 2 it returns [1.00000]; the answer is [1.50000]. An even window's median is the average of its two middle values, and that can end in .5. Dividing with // floors it. Divide with /.
Adding two ints before dividing (Java). (low.peek() + high.peek()) / 2.0
On nums = [2147483647, 2147483647], k = 2 it returns [-1.00000]; the answer is [2147483647.00000]. low.peek() + high.peek() adds two ints, and 2,147,483,647 + 2,147,483,647 overflows to −2 before the division sees a double. Turn one into a double first: ((double) low.peek() + high.peek()) / 2.
Balancing the halves by size alone. if n_low <= n_high:
On nums = [1, 5, 10], k = 3 it returns [10.00000]; the answer is [5.00000]. A new value has to go to the half its value belongs in. Putting it in whichever half is smaller breaks the order between the halves: here the 10 goes into the lower half and becomes its top, so the median reads 10 instead of 5. Compare with the lower half's top first.
Counting a deleted top out of the wrong half. if x < -low[0]:
On nums = [2, 1, 3], k = 2 it returns [1.50000, 1.50000]; the answer is [1.50000, 2.00000]. A value equal to the lower half's top belongs to the lower half, so the test is x <= -low[0]. With <, deleting that value takes one from the upper half's count while the value itself stays on the lower half's top. The counts no longer match the heaps, and the medians drift.
Cleaning a top only when deleting. heapq.heappush(high, -heapq.heappop(low))
On nums = [2, 1, 1, 1, 3, 3], k = 3 it returns [1.00000, 1.00000, 1.00000, 2.00000]; the answer is [1.00000, 1.00000, 1.00000, 3.00000]. Moving a top across can uncover a deleted value underneath it. If the half isn't cleaned after the move, that dead value sits on top and is read as the median. Clean after every move, so both tops are always live.
Where This Pattern Is Taught
This problem practises two heaps for a running median, with deletes done late. It's taught in Two Heaps: the Running Median, with the sorted window it beats as k grows, and the overflow bug that two 2,147,483,647s catch.