Sliding Window Median

HardTwo Heaps · Sliding Window · Ordered Set🧩 Two Heaps LeetCode #480 ↗Updated Oct 30, 2026

Problem

A window of size k slides one step at a time from the left end of nums to the right end. For every position, report the median of the k numbers inside it (the middle value when sorted, or the average of the two middle values when k is even). Return the medians as a double[]; answers within 10^-5 are accepted.

Inputnums = [1,3,-1,-3,5,3,6,7], k = 3Output[1.0,-1.0,-1.0,3.0,5.0,6.0]

Inputnums = [1,2,3,4,2,3,1,4,2], k = 4Output[2.5,2.5,3.0,2.5,2.5,2.5]

1 ≤ k ≤ n ≤ 10⁵ · -2³¹ ≤ nums[i] ≤ 2³¹ - 1

Try it yourself

Java

class Solution {
    public double[] medianSlidingWindow(int[] nums, int k) {
        
    }
}

Your code is saved in this browser.Submit on LeetCode ↗

Key insight

Split the window into a lower half and an upper half kept in ordered sets; the median lives at their boundary. Sliding is just one insert, one delete and a rebalance — using an ordered set of indices makes deleting the outgoing element O(log k), which plain heaps cannot do.

PatternTwo Heaps

Instinct When you need the middle of a changing collection, or best-of-one-pile fed by another pile, split it into a max-heap low half and a min-heap high half.

Memory hack Small fries in a max-heap, big fish in a min-heap; the median lives on the shoreline between them.

Open the Two Heaps guide →

Approaches

Brute ForceCopy and Sort Every Window

Time O(n · k log k)Space O(k)

For each start i, copy nums[i..i+k-1], sort it and read the middle. Average the two middles in double so huge values cannot overflow.

Java

public double[] medianSlidingWindow(int[] nums, int k) {
    double[] res = new double[nums.length - k + 1];
    for (int i = 0; i + k <= nums.length; i++) {
        int[] w = Arrays.copyOfRange(nums, i, i + k);
        Arrays.sort(w);
        res[i] = k % 2 == 1 ? w[k / 2] : ((double) w[k / 2 - 1] + w[k / 2]) / 2.0;
    }
    return res;
}

Clear baseline; re-sorting k elements per step is wasted work.

BetterMaintain One Sorted Window Array

Time O(n · k)Space O(k)

Sort the first window once. On each slide, binary-search the outgoing value and shift it out, then binary-search the incoming value's slot and shift it in. The array stays sorted, so the median is a direct index read; only the shifts cost O(k).

Java

public double[] medianSlidingWindow(int[] nums, int k) {
    int n = nums.length;
    double[] res = new double[n - k + 1];
    int[] win = Arrays.copyOf(nums, k);
    Arrays.sort(win);
    for (int i = 0; ; i++) {
        res[i] = k % 2 == 1 ? win[k / 2] : ((double) win[k / 2 - 1] + win[k / 2]) / 2.0;
        if (i + k == n) break;
        // remove the outgoing value (any matching copy is fine)
        int pos = Arrays.binarySearch(win, nums[i]);
        System.arraycopy(win, pos + 1, win, pos, k - 1 - pos);
        // insert the incoming value into the sorted prefix win[0..k-2]
        int x = nums[i + k];
        int ins = Arrays.binarySearch(win, 0, k - 1, x);
        if (ins < 0) ins = -ins - 1;
        System.arraycopy(win, ins, win, ins + 1, k - 1 - ins);
        win[ins] = x;
    }
    return res;
}

Big constant-factor win (memmove is fast), but still O(k) per step.

OptimalTwo Ordered Sets of Indices (Two-Heap Idea)

Time O(n log k)Space O(k)

lo holds the smaller half (size ⌈k/2⌉), hi the larger half, both as TreeSets of indices ordered by (value, index) so duplicates stay distinct. Insert the new index on the correct side, delete the outgoing index from whichever set has it, then rebalance by moving boundary elements. The median is lo.last() or the average of lo.last() and hi.first().

Java

public double[] medianSlidingWindow(int[] nums, int k) {
    Comparator<Integer> byValue = (a, b) ->
        nums[a] != nums[b] ? Integer.compare(nums[a], nums[b]) : Integer.compare(a, b);
    TreeSet<Integer> lo = new TreeSet<>(byValue), hi = new TreeSet<>(byValue);
    double[] res = new double[nums.length - k + 1];
    for (int i = 0; i < nums.length; i++) {
        if (lo.isEmpty() || byValue.compare(i, lo.last()) < 0) lo.add(i);
        else hi.add(i);
        if (i >= k && !lo.remove(i - k)) hi.remove(i - k);
        // rebalance: lo has the same size as hi, or one more
        while (lo.size() > hi.size() + 1) hi.add(lo.pollLast());
        while (hi.size() > lo.size()) lo.add(hi.pollFirst());
        if (i >= k - 1) {
            res[i - k + 1] = k % 2 == 1 ? nums[lo.last()]
                : ((double) nums[lo.last()] + nums[hi.first()]) / 2.0;
        }
    }
    return res;
}

Dry runnums = [1,3,-1,-3,5,3,6,7], k = 3

m median = lo.last() changed

i=2
1
m
3

-1

-3

5

3

6

7

lo{-1,1} hi{3} → 1
i=3
1

3

-1
m
-3

5

3

6

7

lo{-3,-1} hi{3} → -1
i=4
1

3

-1
m
-3

5

3

6

7

lo{-3,-1} hi{5} → -1
i=5
1

3

-1

-3

5

3
m
6

7

lo{-3,3} hi{5} → 3
i=6
1

3

-1

-3

5
m
3

6

7

lo{3,5} hi{6} → 5
i=7
1

3

-1

-3

5

3

6
m
7

lo{3,6} hi{7} → 6

Logarithmic per slide with exact deletions — no lazy-deletion bookkeeping.

Pro tip

With two PriorityQueues you'd need lazy deletion (a hash map of “to delete” counts); index-keyed TreeSets avoid that entirely.

At a glance

Level	Approach	Time	Space
Brute Force	Copy and Sort Every Window	`O(n · k log k)`	`O(k)`
Better	Maintain One Sorted Window Array	`O(n · k)`	`O(k)`
Optimal	Two Ordered Sets of Indices (Two-Heap Idea)	`O(n log k)`	`O(k)`

Common pitfalls

(a + b) / 2 in int overflows for values near 2³¹ — cast to double first.
A TreeSet of values silently drops duplicates; store indices and break ties by index.
PriorityQueue.remove(Object) is O(k), quietly turning the heap solution into O(n·k).

Interview tips

Build on Find Median from Data Stream (295): same two halves, plus deletions.
State the balance invariant (|lo| = |hi| or |hi| + 1) and check it after every slide.
Ask about precision — returning doubles with 10^-5 tolerance is the norm.

Pattern

Two heaps / two ordered halves → running median or k-th order statistic under inserts and deletes.

My notes saved in this browser