Sliding Window Median
Mahabharata — The Moving Balance — Median of a Sliding Window as the View Shifts
खिड़की सरकती है — माध्य बदलता है। आलसी निष्कासन — हटाया तत्व बाद में जाएगा॥
*The window slides — the median changes. Lazy removal — the ejected element leaves later.*
The Story
Find the median of each sliding window of size k in an array.
For `nums=[1,3,-1,-3,5,3,6,7]`, k=3: medians=[1,-1,-1,3,5,6].
**Two-Heap + Lazy Deletion:** - Same two-heap structure as hp-16 (lo: max-heap, hi: min-heap) - When a number leaves the window: mark it as 'to-delete' in a lazy deletion map - Before using heap tops (for median/rebalance): remove lazily deleted elements from the top
```java TreeMap<Integer,Integer> lo = new TreeMap<>(Collections.reverseOrder()); // max at first TreeMap<Integer,Integer> hi = new TreeMap<>(); // min at first int loSize=0, hiSize=0; // Or use two PriorityQueues with a 'dead' HashMap for lazy deletion ```
Alternative with TreeMap (acts as sorted multiset): - TreeMap supports O(log k) add/remove/min/max - No lazy deletion needed — direct remove
```java TreeMap<Integer,Integer> lo = new TreeMap<>(); // lower half (want max) TreeMap<Integer,Integer> hi = new TreeMap<>(); // upper half (want min) // add: similar two-heap logic // remove: remove from whichever half it's in // rebalance after each add/remove ```
For each window: 1. Add nums[i] to the structure 2. Rebalance 3. Record median 4. Remove nums[i-k] from the structure 5. Rebalance
The Sort-Each-Window Approach
For each window: sort k elements, return middle. O(nk log k).
public double[] medianSlidingWindowBruteForce(int[] nums, int k) {
double[] res = new double[nums.length-k+1];
for (int i=0;i<=nums.length-k;i++) {
int[] w=Arrays.copyOfRange(nums,i,i+k);
Arrays.sort(w);
res[i]=k%2==1?w[k/2]:(w[k/2-1]+(long)w[k/2])/2.0;
}
return res;
}The Two-TreeMap Lazy Wisdom
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;
double[] res = new double[nums.length - k + 1];
for (int i = 0; i < nums.length; i++) {
// Add nums[i]
int n = nums[i];
if (loSize == 0 || n <= lo.firstKey()) { lo.merge(n, 1, Integer::sum); loSize++; }
else { hi.merge(n, 1, Integer::sum); hiSize++; }
// Rebalance
while (loSize > hiSize + 1) { int v=lo.firstKey(); hi.merge(v,1,Integer::sum); hiSize++; removeFrom(lo,v); loSize--; }
while (hiSize > loSize) { int v=hi.firstKey(); lo.merge(v,1,Integer::sum); loSize++; removeFrom(hi,v); hiSize--; }
if (i >= k - 1) {
// Get median
res[i-k+1] = loSize>hiSize ? lo.firstKey() : (lo.firstKey()+(long)hi.firstKey())/2.0;
// Remove outgoing nums[i-k+1]
int out = nums[i-k+1];
if (lo.containsKey(out)) { removeFrom(lo,out); loSize--; }
else { removeFrom(hi,out); hiSize--; }
// Rebalance
while (loSize > hiSize + 1) { int v=lo.firstKey(); hi.merge(v,1,Integer::sum); hiSize++; removeFrom(lo,v); loSize--; }
while (hiSize > loSize) { int v=hi.firstKey(); lo.merge(v,1,Integer::sum); loSize++; removeFrom(hi,v); hiSize--; }
}
}
return res;
}
void removeFrom(TreeMap<Integer,Integer> map, int key) {
if (map.merge(key,-1,Integer::sum) == 0) map.remove(key);
}Step-by-Step Walkthrough
[2,3,4], k=2
i=0: add 2 → lo={2:1},size1
i=1: add 3 → hi.merge, rebalance → lo={2},hi={3}. Median=(2+3)/2=2.5. Remove 2 → lo={},hi={3}. Rebalance.
i=2: add 4 → lo={3},hi={4}. Median=(3+4)/2=3.5. Remove 3.
Result=[2.5,3.5] ✅Deep Insight
**TreeMap as sorted multiset:** Java's TreeMap<Integer,Integer> stores (value → count) pairs. It supports O(log k) firstKey() (minimum or maximum depending on order), and O(log k) merge/remove. This provides the same two-heap functionality but with direct removal — no lazy deletion needed.
**The rebalance invariant:** lo.size = hi.size (even count) or lo.size = hi.size + 1 (odd count). Maintain after every add and remove.
**Integer overflow:** When computing (lo.max + hi.min) / 2.0, cast to long first: `(lo.firstKey() + (long)hi.firstKey()) / 2.0`.
Complexity Analysis
| Approach | Time | Space | Note |
|---|---|---|---|
| Brute Force | O(nk log k) | O(k) | Sort each window |
| Optimal | O(n log k) | O(k) | n additions+removals, each O(log k) in TreeMap |
Pattern Recognition
✅ Sliding window median = two-heap (hp-16) + deletion support ✅ TreeMap as sorted multiset for direct removal ✅ Rebalance after both add AND remove ✅ Watch for integer overflow in median calculation **LeetCode Trigger Phrases:** → "sliding window median" → Online median with evictions → Two-heap with deletion
Bhagavad Gita 6.23
तं विद्याद् दुःखसंयोगवियोगं योगसंज्ञितम्।
Know that which is called yoga to be the disconnection from the union with suffering.
Connection: The sliding window continuously releases old values and embraces new ones — a constant flow of entry and exit. The median, maintained through this flux, represents the current balance point of the window's contents. Like yoga that frees one from attachment to both pleasure and suffering, the two-TreeMap structure neither clings to departing values nor is overwhelmed by arrivals — it maintains equanimous balance (the median) through every transition.