Sliding Window Median

class Solution {
public:
    vector<double> medianSlidingWindow(vector<int>& nums, int k) {
        multiset<int> lo, hi;
        auto median = [&](){
            if (k & 1) return (double)*lo.rbegin();
            return ((double)*lo.rbegin() + *hi.begin()) / 2.0;
        };
        auto add = [&](int x){
            if (lo.empty() || x <= *lo.rbegin()) lo.insert(x);
            else hi.insert(x);
            if (lo.size() > hi.size() + 1) {
                hi.insert(*lo.rbegin());
                lo.erase(prev(lo.end()));
            } else if (hi.size() > lo.size()) {
                lo.insert(*hi.begin());
                hi.erase(hi.begin());
            }
        };
        auto erase = [&](int x){
            if (auto it = lo.find(x); it != lo.end()) lo.erase(it);
            else hi.erase(hi.find(x));
            if (lo.size() > hi.size() + 1) {
                hi.insert(*lo.rbegin());
                lo.erase(prev(lo.end()));
            } else if (hi.size() < lo.size() - 1 || (lo.size() < hi.size())) {
                lo.insert(*hi.begin());
                hi.erase(hi.begin());
            }
        };
        vector<double> ans;
        for (int i = 0; i < (int)nums.size(); ++i) {
            add(nums[i]);
            if (i >= k) erase(nums[i - k]);
            if (i >= k - 1) ans.push_back(median());
        }
        return ans;
    }
};

import "container/heap"

// maxHeap and minHeap of ints with lazy deletion via a deferred-removal map.
type lazyMaxHeap struct {
    data []int
    rm   map[int]int
    size int
}

func (h lazyMaxHeap) Len() int            { return len(h.data) }
func (h lazyMaxHeap) Less(i, j int) bool  { return h.data[i] > h.data[j] }
func (h lazyMaxHeap) Swap(i, j int)       { h.data[i], h.data[j] = h.data[j], h.data[i] }
func (h *lazyMaxHeap) Push(x interface{}) { h.data = append(h.data, x.(int)) }
func (h *lazyMaxHeap) Pop() interface{} {
    n := len(h.data)
    v := h.data[n-1]
    h.data = h.data[:n-1]
    return v
}
func (h *lazyMaxHeap) prune() {
    for len(h.data) > 0 && h.rm[h.data[0]] > 0 {
        h.rm[h.data[0]]--
        heap.Pop(h)
    }
}
func (h *lazyMaxHeap) top() int { h.prune(); return h.data[0] }

type lazyMinHeap struct {
    data []int
    rm   map[int]int
    size int
}

func (h lazyMinHeap) Len() int            { return len(h.data) }
func (h lazyMinHeap) Less(i, j int) bool  { return h.data[i] < h.data[j] }
func (h lazyMinHeap) Swap(i, j int)       { h.data[i], h.data[j] = h.data[j], h.data[i] }
func (h *lazyMinHeap) Push(x interface{}) { h.data = append(h.data, x.(int)) }
func (h *lazyMinHeap) Pop() interface{} {
    n := len(h.data)
    v := h.data[n-1]
    h.data = h.data[:n-1]
    return v
}
func (h *lazyMinHeap) prune() {
    for len(h.data) > 0 && h.rm[h.data[0]] > 0 {
        h.rm[h.data[0]]--
        heap.Pop(h)
    }
}
func (h *lazyMinHeap) top() int { h.prune(); return h.data[0] }

func medianSlidingWindow(nums []int, k int) []float64 {
    rmLo := map[int]int{}
    rmHi := map[int]int{}
    lo := &lazyMaxHeap{rm: rmLo}
    hi := &lazyMinHeap{rm: rmHi}

    median := func() float64 {
        if k&1 == 1 {
            return float64(lo.top())
        }
        return (float64(lo.top()) + float64(hi.top())) / 2.0
    }
    rebalance := func() {
        for lo.size > hi.size+1 {
            v := lo.top()
            heap.Pop(lo)
            heap.Push(hi, v)
            lo.size--
            hi.size++
        }
        for hi.size > lo.size {
            v := hi.top()
            heap.Pop(hi)
            heap.Push(lo, v)
            hi.size--
            lo.size++
        }
    }
    add := func(x int) {
        if lo.size == 0 || x <= lo.top() {
            heap.Push(lo, x)
            lo.size++
        } else {
            heap.Push(hi, x)
            hi.size++
        }
        rebalance()
    }
    erase := func(x int) {
        if lo.size > 0 && x <= lo.top() {
            rmLo[x]++
            lo.size--
        } else {
            rmHi[x]++
            hi.size--
        }
        lo.prune()
        hi.prune()
        rebalance()
    }

    ans := []float64{}
    for i := 0; i < len(nums); i++ {
        add(nums[i])
        if i >= k {
            erase(nums[i-k])
        }
        if i >= k-1 {
            ans = append(ans, median())
        }
    }
    return ans
}

from sortedcontainers import SortedList
from typing import List

class Solution:
    def medianSlidingWindow(self, nums: List[int], k: int) -> List[float]:
        window = SortedList(nums[:k])
        ans: List[float] = []
        mid = k // 2
        if k & 1:
            ans.append(float(window[mid]))
        else:
            ans.append((window[mid - 1] + window[mid]) / 2.0)
        for i in range(k, len(nums)):
            window.remove(nums[i - k])
            window.add(nums[i])
            if k & 1:
                ans.append(float(window[mid]))
            else:
                ans.append((window[mid - 1] + window[mid]) / 2.0)
        return ans

function medianSlidingWindow(nums, k) {
    const window = nums.slice(0, k).sort((a, b) => a - b);
    const bsLeft = (arr, x) => {
        let lo = 0, hi = arr.length;
        while (lo < hi) {
            const mid = (lo + hi) >> 1;
            if (arr[mid] < x) lo = mid + 1;
            else hi = mid;
        }
        return lo;
    };
    const mid = k >> 1;
    const median = () => k & 1 ? window[mid] : (window[mid - 1] + window[mid]) / 2;
    const ans = [median()];
    for (let i = k; i < nums.length; i++) {
        const out = bsLeft(window, nums[i - k]);
        window.splice(out, 1);
        const ins = bsLeft(window, nums[i]);
        window.splice(ins, 0, nums[i]);
        ans.push(median());
    }
    return ans;
}

class Solution {
    private TreeMap<Integer, Integer> lo;
    private TreeMap<Integer, Integer> hi;
    private int loSize, hiSize;
    private int k;

    private void addTo(TreeMap<Integer, Integer> m, int x) {
        m.merge(x, 1, Integer::sum);
    }

    private void removeFrom(TreeMap<Integer, Integer> m, int x) {
        int c = m.get(x);
        if (c == 1) m.remove(x); else m.put(x, c - 1);
    }

    private double median() {
        if ((k & 1) == 1) return (double) lo.lastKey();
        return ((double) lo.lastKey() + (double) hi.firstKey()) / 2.0;
    }

    private void rebalance() {
        while (loSize > hiSize + 1) {
            int v = lo.lastKey();
            removeFrom(lo, v);
            loSize--;
            addTo(hi, v);
            hiSize++;
        }
        while (hiSize > loSize) {
            int v = hi.firstKey();
            removeFrom(hi, v);
            hiSize--;
            addTo(lo, v);
            loSize++;
        }
    }

    private void add(int x) {
        if (loSize == 0 || x <= lo.lastKey()) {
            addTo(lo, x);
            loSize++;
        } else {
            addTo(hi, x);
            hiSize++;
        }
        rebalance();
    }

    private void erase(int x) {
        if (lo.containsKey(x)) {
            removeFrom(lo, x);
            loSize--;
        } else {
            removeFrom(hi, x);
            hiSize--;
        }
        rebalance();
    }

    public double[] medianSlidingWindow(int[] nums, int k) {
        this.k = k;
        lo = new TreeMap<>();
        hi = new TreeMap<>();
        loSize = 0;
        hiSize = 0;
        double[] ans = new double[nums.length - k + 1];
        int idx = 0;
        for (int i = 0; i < nums.length; i++) {
            add(nums[i]);
            if (i >= k) erase(nums[i - k]);
            if (i >= k - 1) ans[idx++] = median();
        }
        return ans;
    }
}

function medianSlidingWindow(nums: number[], k: number): number[] {
    const window: number[] = nums.slice(0, k).sort((a, b) => a - b);
    const bsLeft = (arr: number[], x: number): number => {
        let lo = 0, hi = arr.length;
        while (lo < hi) {
            const mid = (lo + hi) >> 1;
            if (arr[mid] < x) lo = mid + 1;
            else hi = mid;
        }
        return lo;
    };
    const mid = k >> 1;
    const median = (): number => k & 1 ? window[mid] : (window[mid - 1] + window[mid]) / 2;
    const ans: number[] = [median()];
    for (let i = k; i < nums.length; i++) {
        const out = bsLeft(window, nums[i - k]);
        window.splice(out, 1);
        const ins = bsLeft(window, nums[i]);
        window.splice(ins, 0, nums[i]);
        ans.push(median());
    }
    return ans;
}