Problem link ও উৎস
- **Original source:** Running median over a fixed-size window (two heaps + lazy deletion)
- **Platform:** LeetCode —
- **Topic:** heap / priority queue
- **Difficulty:** Hard
- **Pattern:** Two heaps (lower max-heap + upper min-heap) + lazy deletion + rebalancing
- **Basic idea inherited from:** `08` two heaps + lazy deletion — `018`-এর running median + window-এর জন্য element সরানো
## প্রশ্ন ও উদাহরণ {#problem}
### সহজ করে প্রশ্ন {#1-problem-in-simple-words}
একটা array `nums` আর একটা window-আকার `k` দেওয়া। window বাঁ থেকে ডানে এক ঘর করে সরছে। প্রতিটা position-এ window-এর ভেতরের `k`-টা সংখ্যার **median** বের করতে হবে। `k` বিজোড় হলে median = মাঝেরটা; জোড় হলে মাঝের দুটোর গড়। সব position-এর median গুলো একটা list-এ ফেরত দাও।
```text
nums = [1, 3, -1, -3, 5, 3, 6, 7], k = 3
window গুলোর median -> [1, -1, -1, 3, 5, 6]
```
### Input ও output {#8-example-input-and-output}
```text
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)
```
### চেনা উদাহরণে বোঝা {#6-real-life-analogy}
ভাবো একটা চলন্ত দাঁড়িপাল্লা (seesaw)। বাঁ পাল্লায় ছোট সংখ্যা, ডান পাল্লায় বড় — median মাঝখানে। window সরলে ডান দিক থেকে নতুন এক জন উঠছে, বাঁ দিক থেকে এক জন নামছে। কিন্তু পাল্লার মাঝখান থেকে কাউকে টেনে নামানো ঝামেলা — তাই তাকে শুধু "চলে যাওয়ার তালিকা"-য় টিক দাও; কিনারায় চলে এলে তবেই সত্যিকারে নামাও। পাল্লা দুটো প্রায় সমান ভারী রাখো — মাঝখানের value(s), মানে median, সবসময় হাতের নাগালে।
## ভিত্তির ধারণা {#idea}
### আগের কোন ধারণাটি লাগবে {#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 পেতে শুধু দুই অর্ধের boundary লাগে। Heap balance করা এবং stale top সরানোর পরে এই boundary থেকে O(1)-এ median পড়া যায়। Window সরলে নতুন value push হয়, আর পুরোনো value মুছে দেওয়ার জন্য mark করা হয়। এই implementation-এ heap-এর নিচে stale entry জমতে পারে, তাই physical heap size সবসময় k নয়। Worst-case মোট সময় O(n log n); প্রতিটি window নতুন করে sort করতে হয় না।
## ধাপে ধাপে সমাধান {#walkthrough}
### প্রথম সরল উপায় {#9-brute-force-thinking}
প্রথম সরল চিন্তা: প্রতিটা window-এর জন্য তার `k`-টা element আলাদা করে নাও, sort করো, মাঝের element (বা দুটোর গড়) median হিসেবে নাও। window এক ঘর সরলেই আবার পুরো sort।
```text
প্রতি window: slice নাও -> sort -> মাঝখান নাও
n-k+1 টা window x প্রতিটায় O(k log k) 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 ভরুন এবং valid size দিয়ে balance রাখুন। প্রতি slide-এ পুরোনো value-কে `to_delete`-এ mark করে তার অর্ধের valid size কমান, নতুন value insert করুন, balance ঠিক করুন এবং stale top সরান। k বিজোড় হলে lower-এর top, জোড় হলে দুই top-এর গড় নিন। নিচের code নতুন value যোগ করার পরে পূর্ণ window-এর median নেয় এবং পরের window-এর জন্য পুরোনো value সরায়; একই window-সীমা বজায় থাকে। Rebuild ছাড়া lazy deletion-এ মোট worst-case O(n log n)।
### ভাবনার পরিবর্তন {#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)-এর মিলন।
### ছবিতে বোঝা {#7-visual-explanation}
`nums = [1,3,-1,-3,5,3,6,7], k = 3` — lower max-heap, upper min-heap (effective view):
```text
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]
```
### ছোট input-এ ধাপে ধাপে {#14-step-by-step-dry-run}
Input `nums = [1, 2, 3, 4], k = 2` (জোড় k, তাই median = দুই top-এর গড়):
1. প্রথম window `[1, 2]`: insert 1, insert 2, balance → lower top 1, upper top 2; median = (1+2)/2 = 1.5
2. 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
3. slide → window `[3, 4]`: পুরোনো 2 বাদ (lazy mark); নতুন 4 insert; balance; ঝাড়া → lower top 3, upper top 4; median = (3+4)/2 = 3.5
4. আর slide নেই → return [1.5, 2.5, 3.5]
## কোড ও ব্যাখ্যা {#code}
### Python {#15-python-solution}
```python
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 করি।
### Output মিলিয়ে দেখা {#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!`।
## খরচ ও সাধারণ ভুল {#cost}
### সময় {#18-time-complexity}
**O(n log n) worst case, এই implementation-এর জন্য।** মোট add, rebalance এবং stale-pop operation O(n), কিন্তু physical heap-এ stale entry-সহ O(n) item থাকতে পারে। তাই heap operation-এর bound O(log n)। Top পরিষ্কার ও balance ঠিক থাকলে median পড়া O(1)। Heap-এর আকার O(k)-তে রাখতে periodic rebuild বা সরাসরি deletion সমর্থনকারী structure যোগ করলে O(n log k) অর্জন করা যায়; এখানে সে ব্যবস্থা নেই।
### অতিরিক্ত জায়গা {#19-space-complexity}
**O(n) worst-case auxiliary space।** Valid element বড়জোর kটি হলেও stale entry ও deletion map বড় হতে পারে। যেমন increasing input-এ পুরোনো ছোট value lower max-heap-এর নিচে থেকে যায়, top-এ আসে না বলে সঙ্গে সঙ্গে মুছে যায় না। Output 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_delete` heap-নিরপেক্ষ — তাই remove-এ যে অর্ধের size কমালে, সেই অর্ধেই সঙ্গে সঙ্গে prune না করলে credit ভুল heap-এ খরচ হয়ে size desync হয় (খালি heap-এ pop → IndexError)।
## শেখা ও পরের অনুশীলন {#practice}
### ভিত্তির সঙ্গে সম্পর্ক {#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 —