coding challenges · advanced

Sliding-Window Median (Median of the Last K)

Asked at MCX India: stream of trade prices, return the median over the last K at every tick in O(log K) time / O(K) space. Maintain two multisets — lo (lower half, max at rbegin) and hi (upper half, min at begin) — kept balanced to within one element; the median is the boundary value (max(lo) when K is odd, the average of max(lo) and min(hi) when K is even). Each tick inserts the new price, erases the price leaving the window by value (multiset.erase(find(x)) removes one occurrence, so duplicates are fine), and rebalances. Two heaps work too but need lazy deletion to evict the leaving element; multisets erase by value directly. For prices [5,15,1,3,2,8,7,9,10,6] and K=4 the output is 4.0 2.5 2.5 5.0 7.5 8.5 8.0.

🔑 Key line

Sliding-window median = two balanced multisets (lower/upper half); median is the boundary (O(1) read). Each tick: insert new, erase the leaving value, rebalance — all O(log K), O(K) space. Multisets beat two-heaps because erase-by-value avoids lazy deletion and handles duplicate prices.

The code

#include <vector>
#include <set>
#include <cstdio>

// Two multisets split the window: lo = lower half, hi = upper half.
// Median sits at the boundary; each tick is O(log K).
int main() {
    std::vector<int> p = {5, 15, 1, 3, 2, 8, 7, 9, 10, 6};
    int K = 4;
    std::multiset<int> lo, hi;

    auto balance = [&]() {
        while (lo.size() > hi.size() + 1) {
            hi.insert(*lo.rbegin());
            lo.erase(std::prev(lo.end()));
        }
        while (hi.size() > lo.size()) {
            lo.insert(*hi.begin());
            hi.erase(hi.begin());
        }
    };
    auto add = [&](int x) {
        if (lo.empty() || x <= *lo.rbegin())
            lo.insert(x);
        else
            hi.insert(x);
        balance();
    };
    auto remove = [&](int x) {
        auto it = lo.find(x);
        if (it != lo.end())
            lo.erase(it); // erase ONE occurrence (handles duplicates)
        else
            hi.erase(hi.find(x));
        balance();
    };
    auto median = [&]() -> double {
        if (lo.size() > hi.size())
            return *lo.rbegin();
        return (*lo.rbegin() + (double)*hi.begin()) / 2.0;
    };

    for (int i = 0; i < (int)p.size(); ++i) {
        add(p[i]);
        if (i >= K)
            remove(p[i - K]); // drop the price leaving the window
        if (i >= K - 1)
            printf("%.1f ", median());
    }
    printf("\n");
}

What this lesson walks through

01Two sorted halves, median at the seam
02Window full → read the first median
03Slide: drop the oldest, add the newest
04Same machinery, every tick
05Run to the end — all seven medians
06Why multisets, not two heaps

Hold the last K prices as two halves: lo (smaller, max at its end) and hi (larger, min at its start), sizes within one. The median sits at that boundary.

See it animated — step by step, at your own pace

Unlock the full interactive walkthrough of Sliding-Window Median (Median of the Last K) and 100+ animated C++ interview lessons.

Start free →Already a member? Log in →