021 — Sliding Window Median¶
Source¶
- Original source: Running median over a fixed-size window (two heaps + lazy deletion)
- Platform: LeetCode — https://leetcode.com/problems/sliding-window-median/
- Topic: heap / priority queue
- Difficulty: Hard
- Pattern: Two heaps (lower max-heap + upper min-heap) + lazy deletion + rebalancing
- Basic idea inherited from:
08two heaps + lazy deletion —018-এর running median + window-এর জন্য element সরানো
1. Problem in simple words¶
একটা array nums আর একটা window-আকার k দেওয়া। window বাঁ থেকে ডানে এক ঘর করে সরছে। প্রতিটা position-এ window-এর ভেতরের k-টা সংখ্যার median বের করতে হবে। k বিজোড় হলে median = মাঝেরটা; জোড় হলে মাঝের দুটোর গড়। সব position-এর median গুলো একটা list-এ ফেরত দাও।
2. Which basic idea does this inherit from?¶
ভিত 08-এর two heaps (018 Find Median from Data Stream-এর মতো — lower half max-heap, upper half min-heap, balanced) আর তার ওপর নতুন একটা চাল: lazy deletion। stream-এ শুধু যোগ হতো; window-এ একটা পুরোনো element প্রতি step-এ বেরিয়েও যায়। heap-এর মাঝখান থেকে সরাসরি মোছা যায় না, তাই সেটাকে "মুছে ফেলা" বলে চিহ্নিত রেখে, top-এ এলে তবে সত্যিকারে ঝেড়ে ফেলা — এটাই lazy deletion (016 Sliding Window Maximum-এও দেখেছ)।
3. What is the hidden math or logic?¶
লুকানো logic দুই ভাগে। (১) median = balanced দুই অর্ধের কিনারা — ছোট অর্ধের max আর বড় অর্ধের min, যেমন 018-এ। (২) Window সরলে একটা পুরোনো value বাদ দিতে হয়, কিন্তু heap mid থেকে মোছা O(n)। তাই একটা hash-map-এ "কোন value কতবার মুছতে হবে" গুনে রাখি, আর শুধু top যখন এমন একটা মুছে-ফেলা-value হয় তখনই pop করি। সাথে দুই heap-এর effective size balance ধরে রাখি, যাতে top গুলো সত্যিই median ছোঁয়।
4. Which data structure is needed?¶
দুটো heap + একটা hash-map (counter)। (1) lower — ছোট অর্ধের max-heap (negate করা)। (2) upper — বড় অর্ধের min-heap। (3) to_delete — value → কতবার lazily মুছতে হবে, এর dict। সাথে দুটো counter (low_size, up_size) — heap-এ এখনো valid (না-মোছা) কতগুলো element আছে।
5. Why this data structure fits¶
median পেতে দরকার শুধু দুই অর্ধের কিনারা — পুরো sorted window না। দুই heap তা top-এ O(1)-এ দেয়। Window slide-এ একটা add + একটা remove; add হলো push (O(log k)), remove হলো lazy mark (O(1)) + পরে top থেকে ঝাড়া (amortized O(log k))। তাই প্রতি window O(log k)-এ সারা — প্রতিবার window sort করার O(k log k) লাগে না।
6. Real-life analogy¶
ভাবো একটা চলন্ত দাঁড়িপাল্লা (seesaw)। বাঁ পাল্লায় ছোট সংখ্যা, ডান পাল্লায় বড় — median মাঝখানে। window সরলে ডান দিক থেকে নতুন এক জন উঠছে, বাঁ দিক থেকে এক জন নামছে। কিন্তু পাল্লার মাঝখান থেকে কাউকে টেনে নামানো ঝামেলা — তাই তাকে শুধু "চলে যাওয়ার তালিকা"-য় টিক দাও; কিনারায় চলে এলে তবেই সত্যিকারে নামাও। পাল্লা দুটো প্রায় সমান ভারী রাখো — মাঝখানের value(s), মানে median, সবসময় হাতের নাগালে।
7. Visual explanation¶
nums = [1,3,-1,-3,5,3,6,7], k = 3 — lower max-heap, upper min-heap (effective view):
window [1,3,-1] -> sorted {-1,1,3}
lower(max) top = 1 | upper(min) top = 3 median = 1
slide: -1 বের, -3 ঢোকে -> {-3,-1,3}? না, window [3,-1,-3]
sorted {-3,-1,3} -> median = -1
(-1 কে lazy-delete চিহ্ন, top-এ এলে ঝাড়া)
slide: window [-1,-3,5] -> sorted {-3,-1,5} median = -1
slide: window [-3,5,3] -> sorted {-3,3,5} median = 3
slide: window [5,3,6] -> sorted {3,5,6} median = 5
slide: window [3,6,7] -> sorted {3,6,7} median = 6
উত্তর: [1, -1, -1, 3, 5, 6]
8. Example input and output¶
Input : nums=[1,3,-1,-3,5,3,6,7], k=3 -> Output: [1, -1, -1, 3, 5, 6]
Input : nums=[1,2,3,4], k=2 -> Output: [1.5, 2.5, 3.5]
Input : nums=[5], k=1 -> Output: [5.0]
Input : nums=[1,4,2,3], k=4 -> Output: [2.5] (পুরোটাই একটা window)
9. Brute force thinking¶
প্রথম সরল চিন্তা: প্রতিটা window-এর জন্য তার k-টা element আলাদা করে নাও, sort করো, মাঝের element (বা দুটোর গড়) median হিসেবে নাও। window এক ঘর সরলেই আবার পুরো sort।
10. Why brute force is slow¶
প্রতি window-এ পুরো k element sort মানে O(k log k); window সংখ্যা প্রায় n — মোট O(n·k log k), বড় input-এ ভারী। অথচ পরপর দুটো window-এ মাত্র একটা element বদলায় (একটা ঢোকে, একটা বের হয়)। পুরো জিনিস আবার sort করা সেই overlap-টা পুরো নষ্ট করা।
11. Key observation¶
মূল observation: পরপর দুটো window প্রায় পুরোটাই এক — শুধু এক প্রান্তে একটা নতুন value, অন্য প্রান্তে একটা পুরোনো বাদ। তাই পুরো structure আবার বানানোর দরকার নেই; দুই balanced heap-এ একটা insert + একটা delete করলেই median update হয়ে যায়। আর mid থেকে delete-টা lazy করলে heap-এর সস্তা property নষ্ট হয় না।
12. Optimized intuition¶
দুই heap-এ প্রথম window-টা ভরো (insert করে balance রাখো)। তারপর প্রতিটা slide-এ: (১) বেরিয়ে যাওয়া value-কে to_delete-এ মার্ক করো আর সে কোন অর্ধে ছিল বুঝে effective size কমাও; (২) নতুন value insert করো; (৩) balance ঠিক করো; (৪) দুই heap-এর top যদি lazy-deleted হয় তবে ঝেড়ে ফেলো; (৫) median পড়ো (k বিজোড় → lower top; জোড় → দুই top-এর গড়)। প্রতিটা O(log k), মোট O(n log k)।
13. Thinking tweak¶
মোচড়: "window-এর median" না ভেবে ভাবো "018-এর running median, কিন্তু এবার একটা পুরোনো element প্রতি step-এ বিদায় নেয় — heap mid থেকে সরাসরি মোছা যায় না বলে lazy delete করি।" "fixed window + median/order-statistic" শুনলেই দুই heap + lazy deletion মনে করবে; এটা 018 (two heaps) আর 016 (lazy deletion)-এর মিলন।
14. Step-by-step dry run¶
Input nums = [1, 2, 3, 4], k = 2 (জোড় k, তাই median = দুই top-এর গড়):
- প্রথম window
[1, 2]: insert 1, insert 2, balance → lower top 1, upper top 2; median = (1+2)/2 = 1.5 - slide → window
[2, 3]: পুরোনো 1 বাদ (lazy mark, lower-এ ছিল); নতুন 3 insert; balance; top-গুলো থেকে lazy-deleted ঝাড়া → lower top 2, upper top 3; median = (2+3)/2 = 2.5 - slide → window
[3, 4]: পুরোনো 2 বাদ (lazy mark); নতুন 4 insert; balance; ঝাড়া → lower top 3, upper top 4; median = (3+4)/2 = 3.5 - আর slide নেই → return [1.5, 2.5, 3.5]
15. Python solution¶
import heapq
def median_sliding_window(nums, k):
# lower = ছোট অর্ধের max-heap (negate করা), upper = বড় অর্ধের min-heap
lower, upper = [], []
to_delete = {} # lazily-মোছা value -> কতবার মুছতে বাকি
low_size = up_size = 0 # দুই অর্ধে এখনো valid (না-মোছা) কতগুলো
def prune(heap): # top যতক্ষণ মৃত (delete বাকি) ততক্ষণ সত্যিকারে ঝাড়ো
while heap:
val = -heap[0] if heap is lower else heap[0]
if to_delete.get(val, 0) > 0:
to_delete[val] -= 1
heapq.heappop(heap)
else:
break
def balance(): # invariant: valid lower size == upper size বা +1
nonlocal low_size, up_size
if low_size > up_size + 1: # lower-এ বেশি -> একটা upper-এ পাঠাও
prune(lower)
heapq.heappush(upper, -heapq.heappop(lower))
low_size -= 1; up_size += 1
elif low_size < up_size: # upper-এ বেশি -> একটা lower-এ আনো
prune(upper)
heapq.heappush(lower, -heapq.heappop(upper))
up_size -= 1; low_size += 1
prune(lower); prune(upper) # দুই top পরিষ্কার রাখো
def add(x):
nonlocal low_size, up_size
if not lower or x <= -lower[0]: # ছোট অর্ধে যাবে
heapq.heappush(lower, -x); low_size += 1
else: # বড় অর্ধে যাবে
heapq.heappush(upper, x); up_size += 1
balance()
def remove(x):
nonlocal low_size, up_size
to_delete[x] = to_delete.get(x, 0) + 1 # lazy mark
# যে অর্ধে value-টা logically আছে, সেই অর্ধের size কমাও; top হলে এখনই
# prune করো যাতে delete-credit ঠিক জায়গায় খরচ হয় (duplicate-safe)।
if lower and x <= -lower[0]: # lower-অর্ধে ছিল
low_size -= 1
prune(lower)
else: # upper-অর্ধে ছিল
up_size -= 1
prune(upper)
balance()
def median():
if k % 2 == 1:
return float(-lower[0]) # বিজোড়: lower-এর top
return (-lower[0] + upper[0]) / 2.0 # জোড়: দুই top-এর গড়
result = []
for i, x in enumerate(nums):
add(x)
if i >= k - 1: # window পূর্ণ
result.append(median())
remove(nums[i - k + 1]) # সবচেয়ে পুরোনো element বিদায়
return result
# ---- tests ----
assert median_sliding_window([1,3,-1,-3,5,3,6,7], 3) == [1, -1, -1, 3, 5, 6]
assert median_sliding_window([1,2,3,4], 2) == [1.5, 2.5, 3.5]
assert median_sliding_window([5], 1) == [5.0]
assert median_sliding_window([1,4,2,3], 4) == [2.5] # পুরোটাই এক window
assert median_sliding_window([7,7,7], 2) == [7.0, 7.0] # duplicate
print("সব test pass!")
16. Line-by-line code explanation¶
lower, upper = [], []— ছোট অর্ধের max-heap (negate করা) আর বড় অর্ধের min-heap; median এদের top-এ।low_size,up_size— দুই অর্ধে এখনো valid (lazy-মোছা বাদ) কতগুলো element, balance ঠিক রাখতে।prune(heap)— top যতক্ষণ এমন value যার delete বাকি আছে, ততক্ষণ pop করে সত্যিকারে ঝেড়ে ফেলি।balance()— invariant ধরে রাখে: valid lower size সমান বা একটা বেশি; দরকারমতো একটা element এক heap থেকে অন্যটায় সরায়; শেষে দুই top prune করে পরিষ্কার রাখে।add(x)— নতুন value top-এর সাথে তুলনা করে ঠিক অর্ধে push, size বাড়াই, তারপরbalance()।remove(x)— value-কেto_delete-এ গুনে রাখি (lazy mark); সে কোন অর্ধে ছিল বুঝে valid size কমাই, আর top হলে সেই অর্ধেই এখনইpruneকরি (যাতে duplicate value-এর delete-credit ঠিক heap-এ খরচ হয়), তারপরbalance()।median()— k বিজোড় → lower-এর top; জোড় → দুই top-এর গড় (float)।- মূল loop — প্রতিটা element add করি; window পূর্ণ হলে median নিই, তারপর সবচেয়ে পুরোনো element remove করি।
17. Output walkthrough¶
median_sliding_window([1,2,3,4], 2) section 14-এর dry run মেনে [1.5, 2.5, 3.5] দেয় — assert pass। প্রথম example-এ প্রতিটা window-এর সরানো median মিলে [1, -1, -1, 3, 5, 6]। [5], k=1 → একটাই window, median 5.0। [1,4,2,3], k=4 → পুরোটা sorted {1,2,3,4}, মাঝের (2+3)/2 = 2.5। [7,7,7], k=2 → duplicate ঠিকঠাক lazy-delete হয়ে [7.0, 7.0]। median নির্দিষ্ট value, তাই সরাসরি সমতা assert। সব pass-এর পরে print হয়: সব test pass!।
18. Time complexity¶
O(n log k) — প্রতিটা element একবার add, একবার remove; প্রতিটা push/pop O(log k) (heap-এ বড়জোর O(k) entry, lazy-deleted সহ)। lazy-deleted entry গুলো amortized-ভাবে ঝাড়া হয়, তাই গড়ে প্রতিটা operation O(log k)। median O(1)।
19. Space complexity¶
O(k + লাজি-গার্বেজ) — valid element বড়জোর k-টা, কিন্তু এখনো-না-ঝাড়া lazy-deleted entry heap-এ জমে থাকতে পারে; সবচেয়ে খারাপ ক্ষেত্রে O(n) পর্যন্ত যেতে পারে, তবে সাধারণত O(k)-এর কাছাকাছি। আউটপুট list O(n−k+1)।
20. Common mistakes¶
lower-কে max-heap না বানিয়ে সরাসরি heapq — তখন partition উল্টে median ভুল।- valid size আলাদা করে না গোনা, শুধু
len(heap)দিয়ে balance — lazy-deleted entry গুলো গণনায় ঢুকে balance ভেঙে দেয়। - কোন অর্ধ থেকে element বাদ যাচ্ছে ভুল বোঝা — remove-এর সময় value-কে
-lower[0]-এর সাথে তুলনা করে ঠিক অর্ধ নির্ণয় করা জরুরি। - জোড় k-তে integer division (
//) ব্যবহার — median float হতে পারে (যেমন 1.5), তাই/আর2.0। - prune করতে ভুলে যাওয়া — top-এ মৃত value পড়ে থাকলে median বা balance ভুল হয়।
- duplicate value-এর ফাঁদ: একই value যদি দুই heap-এ থাকে,
to_deleteheap-নিরপেক্ষ — তাই remove-এ যে অর্ধের size কমালে, সেই অর্ধেই সঙ্গে সঙ্গে prune না করলে credit ভুল heap-এ খরচ হয়ে size desync হয় (খালি heap-এ pop → IndexError)।
21. Which basic problem this inherits from¶
ভিত্তি 08-এর patterns.md-র Pattern 3 (Two heaps for running median — 018 MedianFinder-এর মতো lower max + upper min) আর Pattern 5/lazy-deletion idea (016 Sliding Window Maximum-এ heap top থেকে stale entry ঝাড়া)। এই দুই pattern একসাথে জুড়লেই sliding window median।
22. Similar harder problems¶
- Find Median from Data Stream — https://leetcode.com/problems/find-median-from-data-stream/ (এই tracker-এর #18; delete নেই, শুধু insert)
- Sliding Window Maximum — https://leetcode.com/problems/sliding-window-maximum/ (#16; lazy deletion + window, কিন্তু max চাই)
- IPO — https://leetcode.com/problems/ipo/ (#19; two heaps, ভিন্ন উদ্দেশ্যে)
23. Pattern learned¶
Two heaps + lazy deletion: balanced দুই heap (lower max + upper min) দিয়ে median ধরে রাখো; window সরলে একটা insert + একটা delete করো, কিন্তু mid থেকে delete-টা "মার্ক করে রাখো, top-এ এলে ঝাড়ো" — lazy। valid size আলাদা গুনে balance রাখো। "fixed window + median/order statistic" পেলেই এই combo।
24. Final summary¶
ভবিষ্যতের আমাকে: sliding window median = 018-এর দুই heap + lazy deletion। প্রতি slide-এ নতুন element add, পুরোনো element-কে to_delete-এ মার্ক করে valid size কমাও, balance ঠিক করো, top থেকে মৃত value ঝাড়ো, তারপর median পড়ো। মনে রেখো — heap mid থেকে সরাসরি মোছা যায় না, তাই lazy; আর balance-এর হিসাব valid (না-মোছা) size দিয়ে করো, raw length দিয়ে নয়।
মনে রাখার নিয়ম (legal): সব নিজের ভাষায় লেখা; problem statement copy করা হয়নি; official link শুধু attribution-এর জন্য; "asked by Google/Amazon" দাবি নেই — এটা একটা common interview pattern।