The O(n) Club: Sliding Window Median: The Interview See-Saw Nobody Warns You About

The O(n) Club: Sliding Window Median—The Interview See-Saw Nobody Warns You About

⚡ TL;DR

Trying to get the median for every sliding window of size k in your array? Sure, you could sort every window and suffocate your CPU, or you could act cool and actually use heaps. Here’s the brute force everyone regrets:

// Brute force: sort every window like you enjoy pain
public double[] medianSlidingWindow(int[] nums, int k) {
    double[] res = new double[nums.length - k + 1];
    for (int i = 0; i <= nums.length - k; i++) {
        int[] window = Arrays.copyOfRange(nums, i, i + k);
        Arrays.sort(window);
        res[i] = (k % 2 == 1)
            ? window[k / 2]
            : ((double) window[k/2 - 1] + window[k/2]) / 2.0;
    }
    return res;
}

🧠 How Devs Usually Mess This Up

Here’s the three-step path to sadness most devs follow:

• Step 1: Sort each window every slide. Spoiler: O(k log k) per slide explodes for big k.
• Step 2: Use a PriorityQueue. Then remember Java heaps are not magical multiset unicorns; try removing an element not at the top (plot twist: it’s slow).
• Step 3: Search for “efficient sliding window median” and confront lazy deletion. Cry. Drink more coffee. Accept your fate.

Basically, unless you’re allergic to passing interviews, you need a better way than sorting. Enter two heaps and some laziness.

🔍 What’s Actually Going On

Imagine your sliding window as the world’s most ADHD see-saw: kids jump on, jump off, and you have to keep it balanced in real time. What you really want—at every moment—is the kid sitting in the middle (the median). Two heaps (a max-heap for the little guys on the left, a min-heap for the big kids on the right) let you always peek at the balance point in O(1).

But… when the window slides, someone leaves. Removing arbitrary elements from a heap is like getting gum out of your hair: messy and slow. So instead, we just pretend the outgoing value’s gone using a HashMap (“lazy deletion”), and we only really clean house at the heap’s top. Out of sight, out of mind—er, out of heap.

🛠️ PseudoCode

• Initialize: Two heaps—maxHeap (for lower half), minHeap (for upper half).
• Process first k numbers:
  • Add to heaps, rebalance if needed, to ensure sizes differ by at most one.
• For each slide:
  • Add new element to correct heap, rebalance everything so the see-saw isn’t broken.
  • Mark outgoing element for lazy deletion.
  • Remove/skip “deleted” items from heap tops only as needed.
  • Fetch the median from the tops: if k is odd, it’s just top of maxHeap; if even, average tops.
• Repeat until you reach the glorious end of the array.

// Rebalancing logic in Java
private void rebalance(PriorityQueue
<integer> lo, PriorityQueue<integer> hi) {
    if (lo.size() > hi.size() + 1) hi.offer(lo.poll());
    else if (hi.size() > lo.size()) lo.offer(hi.poll());
}</integer></integer>

💻 The Code

public double[] medianSlidingWindow(int[] nums, int k) {
    PriorityQueue
<integer> lo = new PriorityQueue<>(Collections.reverseOrder()); // max-heap
    PriorityQueue
<integer> hi = new PriorityQueue<>(); // min-heap
    Map<integer integer> lazy = new HashMap<>(); // lazy removals
    double[] result = new double[nums.length - k + 1];
     for (int i = 0; i < nums.length; i++) {
        // Add
        if (lo.isEmpty() || nums[i] <= lo.peek()) lo.offer(nums[i]);
        else hi.offer(nums[i]);
        // Rebalance
        while (lo.size() > hi.size() + 1) hi.offer(lo.poll());
        while (hi.size() > lo.size()) lo.offer(hi.poll());
        // Remove outgoing element lazily
        if (i >= k) {
            int out = nums[i - k];
            lazy.put(out, lazy.getOrDefault(out, 0) + 1);
            if (out <= lo.peek()) {
                if (lo.peek().equals(out)) lo.poll();
                while (!lo.isEmpty() && lazy.getOrDefault(lo.peek(), 0) > 0) {
                    lazy.put(lo.peek(), lazy.get(lo.peek()) - 1); lo.poll();
                }
            } else {
                if (hi.peek().equals(out)) hi.poll();
                while (!hi.isEmpty() && lazy.getOrDefault(hi.peek(), 0) > 0) {
                    lazy.put(hi.peek(), lazy.get(hi.peek()) - 1); hi.poll();
                }
            }
        }
        if (i >= k - 1) {
            if (k % 2 == 1) result[i - k + 1] = lo.peek();
            else result[i - k + 1] = ((double) lo.peek() + hi.peek()) / 2.0;
        }
    }
    return result;
}</integer></integer></integer>

⚠️ Pitfalls, Traps & Runtime Smacks

• Edge case alert: K is even? Don’t integer-divide your way into rounding errors.
• Duplicates: Don’t be that dev who nukes all copies when only one should be deleted.
• Heap got stale? Always prune lazy-deleted values off the top or you’ll get weird bugs (and medians).
• Complexity: O(N log k) time (because each heap op costs log k; N windows), O(k) extra space. Acceptable unless you’re trying to run this on a potato.

🧠 Interviewer Brain-Tattoo

“You don’t sort windows, you balance them. Unless you like failing tests in O(TLE).”