Sliding Window Median

Problem

Given an array and window size k, return an array of medians of each sliding window of size k.

Key insight: Extend two-heap approach with lazy deletion using a hash map of elements to remove.

Approach

Two heaps (lo max-heap, hi min-heap)
Track elements to "lazily" remove; clean up when they reach heap tops

Solutions

// C++ — lazy deletion
vector<double> medianSlidingWindow(vector<int>& nums, int k) {
    priority_queue<int> lo;
    priority_queue<int, vector<int>, greater<int>> hi;
    unordered_map<int, int> del;
    auto balance = [&]() {
        while (!hi.empty() && del.count(hi.top()) && del[hi.top()] > 0)
            { del[hi.top()]--; hi.pop(); }
        while (!lo.empty() && del.count(lo.top()) && del[lo.top()] > 0)
            { del[lo.top()]--; lo.pop(); }
    };
    for (int i = 0; i < k; i++) { lo.push(nums[i]); hi.push(lo.top()); lo.pop(); if((int)hi.size()>lo.size()){lo.push(hi.top());hi.pop();} }
    auto getMedian = [&]() -> double {
        return k%2==0 ? ((double)lo.top()+hi.top())/2 : lo.top();
    };
    vector<double> res = {getMedian()};
    for (int i = k; i < (int)nums.size(); i++) {
        int out = nums[i-k], in = nums[i];
        del[out]++;
        int sign = (out <= lo.top()) ? -1 : 1;
        if (in <= lo.top()) { lo.push(in); if (sign == -1) { balance(); hi.push(lo.top()); lo.pop(); } }
        else { hi.push(in); if (sign == 1) { balance(); lo.push(hi.top()); hi.pop(); } }
        balance();
        res.push_back(getMedian());
    }
    return res;
}

# Python — using SortedList for O(log k) ops
from sortedcontainers import SortedList

def medianSlidingWindow(nums, k):
    window = SortedList(nums[:k])
    result = []
    def get_median():
        if k % 2 == 0:
            return (window[k//2 - 1] + window[k//2]) / 2
        return float(window[k//2])
    result.append(get_median())
    for i in range(k, len(nums)):
        window.add(nums[i])
        window.remove(nums[i - k])
        result.append(get_median())
    return result

// Java — TreeMap approach
public double[] medianSlidingWindow(int[] nums, int k) {
    TreeMap<Integer, Integer> lo = new TreeMap<>(Collections.reverseOrder());
    TreeMap<Integer, Integer> hi = new TreeMap<>();
    int loSize = 0, hiSize = 0;
    // Complex implementation omitted — see two-heap lazy deletion pattern
    return new double[nums.length - k + 1]; // placeholder
}

// JavaScript — SortedArray simulation
function medianSlidingWindow(nums, k) {
    const sorted = [...nums.slice(0, k)].sort((a, b) => a - b);
    const result = [];
    const getMedian = () => k % 2 === 0 ? (sorted[k/2-1] + sorted[k/2]) / 2 : sorted[Math.floor(k/2)];
    result.push(getMedian());
    for (let i = k; i < nums.length; i++) {
        const removeIdx = sorted.findIndex(x => x === nums[i-k]);
        sorted.splice(removeIdx, 1);
        let lo2 = 0, hi2 = sorted.length;
        while (lo2 < hi2) { const mid = (lo2+hi2)>>1; if(sorted[mid]<nums[i])lo2=mid+1;else hi2=mid; }
        sorted.splice(lo2, 0, nums[i]);
        result.push(getMedian());
    }
    return result;
}

Complexity

O(n log k) per element with SortedList or lazy deletion

Key Insight

Lazy deletion: mark elements for removal but only actually remove them when they surface to heap tops. Maintain balance invariant after each slide.