Sliding Window Median

hard sliding window heap sorting

Problem

Return the median of every length-k contiguous window over the array.

Inputnums = [1,3,-1,-3,5,3,6,7], k = 3

Output[1, -1, -1, 3, 5, 6]

Sort each window of size k and take the middle.

nums

import bisect
def median_sliding_window(nums, k):
    win = sorted(nums[:k])
    out = []
    for i in range(k, len(nums) + 1):
        if k % 2: med = win[k // 2]
        else: med = (win[k // 2 - 1] + win[k // 2]) / 2
        out.append(med)
        if i == len(nums): break
        win.pop(bisect.bisect_left(win, nums[i - k]))
        bisect.insort(win, nums[i])
    return out

function medianSlidingWindow(nums, k) {
  const win = nums.slice(0, k).sort((a, b) => a - b);
  const out = [];
  function median() {
    if (k % 2) return win[(k - 1) / 2];
    return (win[k / 2 - 1] + win[k / 2]) / 2;
  }
  for (let i = k; i <= nums.length; i++) {
    out.push(median());
    if (i === nums.length) break;
    let lo = 0, hi = win.length;
    while (lo < hi) { const m = (lo + hi) >> 1; win[m] < nums[i - k] ? lo = m + 1 : hi = m; }
    win.splice(lo, 1);
    lo = 0; hi = win.length;
    while (lo < hi) { const m = (lo + hi) >> 1; win[m] < nums[i] ? lo = m + 1 : hi = m; }
    win.splice(lo, 0, nums[i]);
  }
  return out;
}

class Solution {
    public double[] medianSlidingWindow(int[] nums, int k) {
        int n = nums.length;
        double[] out = new double[n - k + 1];
        List win = new ArrayList<>();
        for (int i = 0; i < k; i++) win.add(nums[i]);
        Collections.sort(win);
        for (int i = k; i <= n; i++) {
            out[i - k] = k % 2 == 1 ? win.get(k / 2) : ((double) win.get(k / 2 - 1) + win.get(k / 2)) / 2.0;
            if (i == n) break;
            int idx = Collections.binarySearch(win, nums[i - k]);
            win.remove(idx);
            idx = Collections.binarySearch(win, nums[i]);
            if (idx < 0) idx = -idx - 1;
            win.add(idx, nums[i]);
        }
        return out;
    }
}

vector medianSlidingWindow(vector& nums, int k) {
    multiset win(nums.begin(), nums.begin() + k);
    vector out;
    auto med = next(win.begin(), (k - 1) / 2);
    for (int i = k;; i++) {
        out.push_back(k % 2 ? (double) *med : ((double) *med + *next(med)) / 2.0);
        if (i == (int)nums.size()) break;
        win.insert(nums[i]);
        if (nums[i] < *med) med--;
        if (nums[i - k] <= *med) med++;
        win.erase(win.lower_bound(nums[i - k]));
    }
    return out;
}

Explanation

The median of a window is just its middle value once the window is sorted. The idea here is to keep the window always sorted in a list win, so reading the median is instant, and to update that sorted list cheaply as the window slides.

We start by sorting the first k numbers. For an odd k the median is the single middle element win[k // 2]; for an even k it is the average of the two middle elements.

To slide one step, we must remove the number leaving on the left, nums[i - k], and insert the number entering on the right, nums[i]. Both are done with binary search (bisect) so the sorted order is preserved without re-sorting the whole window.

We record a median for every window from index k through the end, breaking out before sliding once we have processed the last one.

Example: nums = [1,3,-1,-3,5,3,6,7], k = 3. The first window [1,3,-1] sorts to [-1,1,3] with median 1; sliding onward yields [1, -1, -1, 3, 5, 6].

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