Definition
- Sliding Window Median – find the median of every contiguous window of size K as the window slides across an array.
- Two heaps – a max-heap for the smaller half and a min-heap for the larger half; the median sits at their boundary.
- Lazy deletion – departing elements are recorded in a count map and physically removed from a heap only when they surface at the top.
- Logical balance – tracked separately from raw heap sizes because lazily deleted elements still take up space.
- Complexity – O(n log n) total time (O(log n) amortized per slide), O(n) space for the heaps and the removal map.
At the National Bank of India, the risk team watches the median transaction amount over the last K transactions as a rolling risk indicator. As each new transaction arrives, the oldest drops out. Rajesh keeps two buckets: a low bucket (max-heap) and a high bucket (min-heap). Rather than hunting for the departing value inside a bucket, he notes it should be ignored and physically drops it only when it bubbles to the top.
Understanding the Concepts
What is the Sliding Window Median problem?
Given an array of numbers and a window size K, compute the median of every contiguous window of K elements as the window slides from left to right. The median of a sorted window is the middle element (odd K) or the average of the two middle elements (even K).
package com.bank.service;
import java.util.*;
public class SlidingWindowMedian {
private PriorityQueue<Integer> maxHeap; // smaller half
private PriorityQueue<Integer> minHeap; // larger half
private Map<Integer, Integer> toRemove;
private int maxHeapSize, minHeapSize;
public double[] medianSlidingWindow(int[] nums, int k) {
maxHeap = new PriorityQueue<>(Collections.reverseOrder());
minHeap = new PriorityQueue<>();
toRemove = new HashMap<>();
maxHeapSize = 0; minHeapSize = 0;
double[] result = new double[nums.length - k + 1];
for (int i = 0; i < nums.length; i++) {
addNum(nums[i]);
if (i >= k) scheduleRemoval(nums[i - k]);
rebalance();
if (i >= k - 1) {
result[i - k + 1] = getMedian(k);
}
}
return result;
}
private void addNum(int num) {
if (maxHeapSize == 0 || num <= maxHeap.peek()) {
maxHeap.offer(num); maxHeapSize++;
} else {
minHeap.offer(num); minHeapSize++;
}
}
private void scheduleRemoval(int num) {
toRemove.merge(num, 1, Integer::sum);
if (num <= maxHeap.peek()) maxHeapSize--;
else minHeapSize--;
}
private void rebalance() {
while (maxHeapSize > minHeapSize + 1) {
minHeap.offer(maxHeap.poll()); maxHeapSize--; minHeapSize++;
pruneTop(maxHeap);
}
while (minHeapSize > maxHeapSize) {
maxHeap.offer(minHeap.poll()); minHeapSize--; maxHeapSize++;
pruneTop(minHeap);
}
pruneTop(maxHeap);
pruneTop(minHeap);
}
private void pruneTop(PriorityQueue<Integer> heap) {
while (!heap.isEmpty() && toRemove.getOrDefault(heap.peek(), 0) > 0) {
toRemove.merge(heap.peek(), -1, Integer::sum);
if (toRemove.get(heap.peek()) == 0) toRemove.remove(heap.peek());
heap.poll();
}
}
private double getMedian(int k) {
if (k % 2 == 1) return maxHeap.peek();
return ((double) maxHeap.peek() + minHeap.peek()) / 2.0;
}
public static void main(String[] args) {
SlidingWindowMedian swm = new SlidingWindowMedian();
int[] txnAmounts = {1000, 3000, 2000, 5000, 4000, 6000};
double[] medians = swm.medianSlidingWindow(txnAmounts, 3);
for (double m : medians) System.out.print(m + " ");
}
}
2000.0 3000.0 4000.0 5000.0
Why is lazy deletion needed?
A PriorityQueue supports efficient removal only at the top (peek/poll). Removing an arbitrary element costs O(n) because the heap must search for it. Lazy deletion avoids this cost: when an element departs the window, you record it in a removal map and physically remove it only when it surfaces at the top of a heap.
// Naive removal: O(n) per window slide
heap.remove(departingValue); // linear scan inside the heap
// Lazy deletion: O(log n) amortized per window slide
toRemove.merge(departingValue, 1, Integer::sum); // schedule for removal
// Physical removal happens only when the value reaches the top:
pruneTop(heap);
Why track logical balance separately?
A lazily deleted element still sits inside the heap and counts toward the raw heap size (heap.size()). If you use raw sizes for rebalancing, the balance is wrong. Instead, you track maxHeapSize and minHeapSize as logical counts that reflect only the elements actually in the current window.
// When scheduling removal:
if (num <= maxHeap.peek()) maxHeapSize--; // logical size decreases
else minHeapSize--;
// The element is still physically in the heap but logically gone
// Rebalancing uses maxHeapSize and minHeapSize, NOT heap.size()
How does pruning the heap tops work?
After rebalancing, you prune both heap tops to ensure the actual top values are valid (not scheduled for removal). This is critical before reading the median.
private void pruneTop(PriorityQueue<Integer> heap) {
while (!heap.isEmpty() && toRemove.getOrDefault(heap.peek(), 0) > 0) {
toRemove.merge(heap.peek(), -1, Integer::sum);
if (toRemove.get(heap.peek()) == 0) toRemove.remove(heap.peek());
heap.poll();
}
}
// This runs whenever a stale value surfaces at the top
// Each element is pruned at most once, so amortized cost stays O(log n)
Why use a count map instead of a set?
The removal structure must handle duplicate values. If the window contains two copies of the same value and only one departs, a set would mark both as removed. A count map keyed by value with an integer count handles duplicates correctly.
// WRONG: using a Set
// toRemoveSet.add(5000); // schedules "5000" for removal
// But if the window has two 5000s, both get removed
// CORRECT: using a count map
// toRemoveMap = {5000: 1} // only one copy scheduled
// When second 5000 departs: toRemoveMap = {5000: 2}
How is the median computed for odd and even K?
When K is odd, the max-heap has one more element than the min-heap, and its top is the median. When K is even, both heaps have equal size, and the median is the average of both tops.
private double getMedian(int k) {
if (k % 2 == 1) return maxHeap.peek(); // odd: max-heap top
return ((double) maxHeap.peek() + minHeap.peek()) / 2.0; // even: average
}
What are the edge cases?
A window of size 1 returns each element as its own median. A window equal to the array length returns a single median. All identical values return that value as every median.
package com.bank.service;
public class MedianEdgeCases {
public static void main(String[] args) {
SlidingWindowMedian swm = new SlidingWindowMedian();
double[] r1 = swm.medianSlidingWindow(new int[]{3, 1, 4}, 1);
for (double v : r1) System.out.print(v + " "); // 3.0 1.0 4.0
System.out.println();
swm = new SlidingWindowMedian();
double[] r2 = swm.medianSlidingWindow(new int[]{5, 5, 5, 5}, 2);
for (double v : r2) System.out.print(v + " "); // 5.0 5.0 5.0
}
}
3.0 1.0 4.0
5.0 5.0 5.0
What are common mistakes?
The most common mistake is using heap.size() for rebalancing instead of logical sizes. This causes incorrect balance because lazily deleted elements inflate the raw size.
// WRONG: using raw heap sizes
while (maxHeap.size() > minHeap.size() + 1) { ... } // counts stale elements
// CORRECT: using logical sizes
while (maxHeapSize > minHeapSize + 1) { ... } // counts only live elements
When should you use this technique?
Use the two-heaps-with-lazy-deletion approach for any sliding window median or quantile problem. In banking, this applies to monitoring the rolling median transaction amount for risk detection.
package com.bank.service;
public class RollingMedianRisk {
public static void main(String[] args) {
int[] recentAmounts = {1500, 2200, 1800, 9500, 2000, 2100, 1900};
SlidingWindowMedian swm = new SlidingWindowMedian();
double[] medians = swm.medianSlidingWindow(recentAmounts, 3);
System.out.print("Rolling medians: ");
for (double m : medians) System.out.printf("%.0f ", m);
}
}
Rolling medians: 1800 2200 2000 2100 2000
What should a senior engineer know?
A senior engineer should explain that each element is added once (O(log n)) and pruned once (O(log n)), giving O(n log n) total. The lazy deletion keeps each slide at amortized O(log n) even though a marked element may sit in the heap for multiple slides. Using a TreeMap instead of two PriorityQueues allows O(log n) arbitrary removal without lazy deletion, at the cost of more complex duplicate handling.
What are common interview follow-up questions?
- Interviewers commonly ask:
- Why lazy deletion? (PriorityQueue does not support efficient arbitrary removal.)
- Why logical sizes? (Lazily deleted elements inflate raw heap sizes.)
- Time complexity? (O(n log n) total, O(log n) amortized per slide.)
- Alternative to lazy deletion? (TreeMap with a comparator that breaks ties by index.)
Visual Overview
Two heaps with lazy deletion:
Window: [1000, 3000, 2000]
┌──────────────┐ ┌──────────────┐
│ maxHeap │ │ minHeap │
│ (smaller) │ │ (larger) │
│ ┌───────┐ │ │ ┌───────┐ │
│ │ 2000 │ ←─┼─median──→│ 3000 │ │
│ │ 1000 │ │ │ └───────┘ │
│ └───────┘ │ │ │
└──────────────┘ └──────────────┘
Median (odd K=3) = maxHeap.peek() = 2000
Slide: remove 1000, add 5000
┌──────────────────────────────────┐
│ Schedule 1000 for lazy removal │
│ toRemove: {1000: 1} │
│ Add 5000 to minHeap │
│ Rebalance + prune │
│ maxHeap: [3000] │
│ minHeap: [5000] │
│ (1000 was pruned from maxHeap) │
│ Median = 3000 │
└──────────────────────────────────┘
Key Takeaway
Sliding Window Median extends the streaming-median two-heaps structure to a fixed window of size K. A max-heap holds the smaller half and a min-heap holds the larger half, with the median sitting at the boundary. The new difficulty is removing the element that ages out of the window, which a priority queue cannot do cheaply for arbitrary values.
Lazy deletion solves this: when an element departs the window, record it in a count map. Physically remove it from the heap only when it surfaces at the top during pruning. Each element is pruned at most once, keeping the amortized cost at O(log n) per slide. Because lazily deleted elements still occupy heap space, track logical heap sizes separately from raw sizes, and prune both tops before reading the median.
The count map (not a set) handles duplicates correctly. If the window contains two copies of the same value and only one departs, the count map decrements by one while a set would mark both as gone.
At the National Bank of India, the risk team monitors the rolling median of the last K transaction amounts. As each new transaction arrives, the oldest one ages out, and the median updates in O(log n) amortized time. The lazy deletion keeps the system responsive even with duplicate amounts and long sliding windows.
Remember one sentence: two heaps for the halves, lazy deletion for the departing element, logical sizes for balance, and prune the tops before reading the median.
---