Sliding Window Median

HardProblemExternal linkUpdated Oct 31, 2026

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 is 1.
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 is 3.
Window [5, 3, 6] sorts to [3, 5, 6]: the median is 5.
Window [3, 6, 7] sorts to [3, 6, 7]: the median is 6.

Sort Every Window — The outlined window, and below it the same values sorted, with the middle in green.

Algorithm

For each start i from 0 to n − k: copy nums[i .. i + k − 1] and sort the copy.
Its median is the average of the values at positions (k − 1) / 2 and k / 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], median 1.
1 leaves from position 1 and -3 goes in at position 0: [-3, -1, 3], median -1.
3 leaves from position 2 and 5 goes in at position 2: [-3, -1, 5], median -1.
-1 leaves from position 1 and 3 goes in at position 1: [-3, 3, 5], median 3.
-3 leaves from position 0 and 6 goes in at position 2: [3, 5, 6], median 5.
5 leaves from position 1 and 7 goes in at position 2: [3, 6, 7], median 6.

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 k values and sort them.
Read the median from the middle.
For each i from k to n − 1: binary search for nums[i − k] and delete it, binary search for the place of nums[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 is 1, so the median is 1.
-3 goes into the lower half; the lower half now has two more, so its top, 1, moves up. 1 leaves the upper half, popped at once. The median is -1.
5 goes into the upper half. 3 leaves the upper half, popped at once. The median is -1.
3 goes into the upper half. -1 leaves the lower half, popped at once; the upper half now has more, so its top, 3, moves down. The median is 3.
6 goes into the upper half. -3 leaves the lower half, marked and left inside its heap; the upper half now has more, so its top, 5, moves down. The median is 5.
7 goes into the upper half. 5 leaves the lower half, popped at once; the upper half now has more, so its top, 6, moves down. The median is 6.

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, and high, 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 low if low is empty or x is at most its top, otherwise into high. Balance.
Remove x: mark it. If x is at most low's top, count it out of low, and if it's low's top, clean low; otherwise do the same with high. Balance.
Balance: if low has two more live values than high, move its top to high and clean low. If high has more live values than low, move its top to low and clean high.
Clean a heap: while its top is marked, pop it and unmark it once.
Median: low's top if low has more live values, otherwise the average of the two tops.
Add the first k values 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.