Sliding Window Median

Problem

Given an array and a window size k, return the median of each sliding window as it moves across the array.

Input:  nums = [1,3,-1,-3,5,3,6,7], k = 3
Output: [1, -1, -1, 3, 5, 6]

Python Solution

import bisect

def median_sliding_window(nums, k):
    window = sorted(nums[:k])
    result = []
    for i in range(k, len(nums) + 1):
        if k % 2 == 1:
            result.append(float(window[k // 2]))
        else:
            result.append((window[k // 2 - 1] + window[k // 2]) / 2.0)
        if i == len(nums):
            break
        outgoing = nums[i - k]
        window.pop(bisect.bisect_left(window, outgoing))
        bisect.insort(window, nums[i])
    return result

C++ Solution

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

Java Solution

class Solution {
    public double[] medianSlidingWindow(int[] nums, int k) {
        TreeMap<Integer, Integer> window = new TreeMap<>();
        for (int i = 0; i < k; i++) window.merge(nums[i], 1, Integer::sum);
        double[] result = new double[nums.length - k + 1];
        for (int i = k; ; i++) {
            result[i - k] = getMedian(window, k);
            if (i == nums.length) break;
            window.merge(nums[i], 1, Integer::sum);
            int out = nums[i - k];
            if (window.merge(out, -1, Integer::sum) == 0) window.remove(out);
        }
        return result;
    }

    private double getMedian(TreeMap<Integer, Integer> window, int k) {
        int count = 0;
        Integer a = null, b = null;
        for (Map.Entry<Integer, Integer> entry : window.entrySet()) {
            count += entry.getValue();
            if (a == null && count >= (k + 1) / 2) a = entry.getKey();
            if (b == null && count >= k / 2 + 1) b = entry.getKey();
            if (a != null && b != null) break;
        }
        return (a + b) / 2.0;
    }
}

Complexity

Time: O(n log k) — each insert/remove into the ordered structure costs O(log k), done once per element. Space: O(k) — the ordered window structure holds exactly k elements.