Problem link ও উৎস
- **Original source:** Classic sliding-window maximum via a max-heap with lazy deletion
- **Platform:** LeetCode —
- **Topic:** heap / priority queue
- **Difficulty:** Hard
- **Pattern:** Lazy deletion (stale entry top-এ এলে তবেই purge)
- **Basic idea inherited from:** `04-stack-and-queue` monotonic deque — সেই idea-র সহজ-মনে-রাখা heap রূপ
## প্রশ্ন ও উদাহরণ {#problem}
### সহজ করে প্রশ্ন {#1-problem-in-simple-words}
একটা array `nums` আর একটা window size `k` দেওয়া। একটা size-`k`-এর window বাঁদিক থেকে ডানদিকে এক ঘর করে slide করে। প্রতিটা window position-এ সেই window-এর **সবচেয়ে বড় element**-টা চাই। সব window-এর maximum গুলো order-এ একটা list-এ return করো। মোট window সংখ্যা `len(nums) - k + 1`।
```text
nums = [1, 3, -1, -3, 5, 3, 6, 7], k = 3 -> [3, 3, 5, 5, 6, 7]
```
### Input ও output {#8-example-input-and-output}
```text
Input : nums=[1,3,-1,-3,5,3,6,7], k=3 -> Output: [3, 3, 5, 5, 6, 7]
Input : nums=[1], k=1 -> Output: [1]
Input : nums=[9,8,7,6], k=2 -> Output: [9, 8, 7] (descending)
Input : nums=[4,4,4,4], k=2 -> Output: [4, 4, 4] (সব সমান)
```
### চেনা উদাহরণে বোঝা {#6-real-life-analogy}
ভাবো একটা পার্টিতে guest list থেকে কারও নাম কাটতে হলে তুমি ভিড়ের মধ্যে গিয়ে তাকে খুঁজে বের করো না — শুধু list-এ নামটা কেটে রাখো। দরজার bouncer (তোমার pop loop) তখনই list দেখে যখন কেউ "সবার আগের লোক" হিসেবে দরজায় পৌঁছায়; নাম কাটা থাকলে তাকে ঢুকতে না দিয়ে সরিয়ে দেয়। সেই "সবার আগের লোক চট করে দাও, stale হলে সরাও" যন্ত্রটাই lazy-deletion heap।
## ভিত্তির ধারণা {#idea}
### আগের কোন ধারণাটি লাগবে {#2-which-basic-idea-does-this-inherit-from}
ভিত `04-stack-and-queue`-এর **monotonic deque**, যেটা এই problem O(n)-এ solve করে। কিন্তু deque-এর invariant মনে রাখা একটু কসরত; heap version হলো সেই idea-র **সহজ-মনে-রাখা, general** রূপ — সাথে `08`-এর **lazy deletion** trick, কারণ heap মাঝখান থেকে সস্তায় delete করতে পারে না।
### ভেতরের যুক্তি {#3-what-is-the-hidden-math-or-logic}
লুকানো logic: heap থেকে arbitrary element delete করা ব্যয়বহুল, তাই **delete-ই করো না**। প্রতিটা element-কে `(value, index)` হিসেবে রাখো। Window সরালে কিছু element "stale" হয়ে যায় (index window-এর বাইরে)। তাদের সাথে সাথে মোছা লাগে না — শুধু যখন তারা heap-এর top-এ ভেসে ওঠে আর আমরা max পড়তে চাই, তখনই purge করো। প্রতিটা element একবার ঢোকে আর বড়জোর একবার বেরোয়।
### কী দিয়ে তথ্য রাখব {#4-which-data-structure-is-needed}
একটা **max-heap of `(value, index)`**। heapq min-heap বলে value negate করি — সবচেয়ে negative মানে সবচেয়ে বড় value। index রাখি যাতে top window-এর ভেতরে আছে কিনা চেক করা যায়।
### এটি কেন উপযুক্ত {#5-why-this-data-structure-fits}
প্রতিটা window-এ দরকার শুধু **max** — পুরো sorted order না। Heap top O(1)-সম max দেয়, push O(log n)। Window সরার সাথে যে element-রা বাইরে গেছে তাদের সাথে সাথে খুঁজে মুছতে গেলে heap-এ O(n); তাই lazy deletion — top-এ stale element এলে তবেই pop। মোট কাজ O(n log n)।
## ধাপে ধাপে সমাধান {#walkthrough}
### প্রথম সরল উপায় {#9-brute-force-thinking}
প্রথম সরল চিন্তা: প্রতিটা window position-এ সেই k-টা element-এর উপর `max()` চালাও।
```text
[1,3,-1] -> 3
[3,-1,-3] -> 3
[-1,-3,5] -> 5
[-3,5,3] -> 5
[5,3,6] -> 6
[3,6,7] -> 7
ফল: [3,3,5,5,6,7]
```
### কোথায় বেশি কাজ হচ্ছে {#10-why-brute-force-is-slow}
প্রতিটা window-এ k element-এর max মানে window-প্রতি O(k), window সংখ্যা O(n) — মোট **O(n·k)**। k বড় হলে এটা প্রায় O(n²)। অথচ পাশাপাশি window-গুলো প্রায় পুরোটাই overlap করে; প্রতিবার শূন্য থেকে max বের করা অপচয়।
### যে বিষয়টি খেয়াল করতে হবে {#11-key-observation}
মূল observation: একটা element একবার heap-এ ঢুকলে আর কখনো নতুন করে ঢোকে না; সে শুধু stale হয়ে top-এ এলে একবার বেরোয়। তাই push/pop মোট O(n)-বার, প্রতিটা O(log n)। "stale top purge" করা ছাড়া আর কোনো deletion লাগে না — heap-এর "শুধু top দেখা যায়" সীমাকেই feature বানানো হলো।
### আরও কম কাজে সমাধান {#12-optimized-intuition}
প্রতিটা index `i`-তে `(-nums[i], i)` heap-এ push করো। window পূর্ণ হলে (`i >= k-1`): যতক্ষণ heap-এর top-এর index `<= i - k` (window-এর বাইরে), pop করে purge করো; তারপর top-এর negated value-ই current window-এর max — সেটা answer-এ যোগ করো। প্রতিটা element একবার push, বড়জোর একবার pop।
### ভাবনার পরিবর্তন {#13-thinking-tweak}
**মোচড়:** "window থেকে element সরানো" না ভেবে ভাবো "stale হয়ে গেলে কিছু করি না; শুধু যখন stale জিনিস top-এ এসে max পড়ায় বাগড়া দেয়, তখনই ঝেড়ে ফেলি।" "sliding window + heap / arbitrary delete / values expire" — এমন কথা শুনলেই lazy deletion-এর কথা মাথায় আসা উচিত।
### ছবিতে বোঝা {#7-visual-explanation}
`nums = [1,3,-1,-3,5,3], k = 3` — max-heap-এ `(-value, index)`; top window-এর বাইরে হলে purge, তারপর max পড়ি:
```text
i=0: push(-1,0) window not full
i=1: push(-3,1) window not full
i=2: push(-(-1),2) top=(-3,1)=val3,idx1 in [0..2] -> max 3
i=3: push(-(-3),3) top=val3,idx1 in [1..3] -> max 3
i=4: push(-5,4) top=(-5,4)=val5 in [2..4] -> max 5
i=5: push(-3,5) top=val5,idx4 in [3..5] -> max 5
answers: [3, 3, 5, 5]
```
### ছোট input-এ ধাপে ধাপে {#14-step-by-step-dry-run}
Input `nums=[9,8,7,6]`, k=2:
1. heap empty, out=[]
2. i=0: push (−9,0); window পূর্ণ নয় (i < k−1=1)
3. i=1: push (−8,1); window পূর্ণ; top (−9,0), idx 0 ≤ i−k = −1? না (0 > −1) → in window; max = 9 → out [9]
4. i=2: push (−7,2); top (−9,0), idx 0 ≤ i−k = 0? হ্যাঁ → pop (stale); top এখন (−8,1), idx 1 ≤ 0? না → max 8 → out [9,8]
5. i=3: push (−6,3); top (−8,1), idx 1 ≤ i−k = 1? হ্যাঁ → pop; top (−7,2), idx 2 ≤ 1? না → max 7 → out [9,8,7]
6. return [9, 8, 7]
## কোড ও ব্যাখ্যা {#code}
### Python {#15-python-solution}
```python
import heapq
def max_sliding_window(nums, k):
heap = [] # (-value, index) — max-heap via negation
out = []
for i, x in enumerate(nums):
heapq.heappush(heap, (-x, i))
if i >= k - 1: # window পূর্ণ হলেই উত্তর লেখা শুরু
# top যদি window-এর বাইরে হয় (stale), লেজি ভাবে purge করো
while heap[0][1] <= i - k:
heapq.heappop(heap)
out.append(-heap[0][0]) # বর্তমান window-এর max
return out
# ---- tests ----
assert max_sliding_window([1, 3, -1, -3, 5, 3, 6, 7], 3) == [3, 3, 5, 5, 6, 7]
assert max_sliding_window([1], 1) == [1] # একটাই element
assert max_sliding_window([9, 8, 7, 6], 2) == [9, 8, 7] # descending
assert max_sliding_window([4, 4, 4, 4], 2) == [4, 4, 4] # সব সমান
assert max_sliding_window([-7, -8, 7, 5, 7, 1, 6, 0], 4) == [7, 7, 7, 7, 7]
print("সব test pass!")
```
### কোডের প্রতিটি অংশ {#16-line-by-line-code-explanation}
- `heap = []` — `(-value, index)`-এর max-heap; negation-এ heapq-কে max দেয়ার মতো বানায়।
- `for i, x in enumerate(nums):` — প্রতিটা element তার index সহ।
- `heapq.heappush(heap, (-x, i))` — প্রতিটা element একবারই heap-এ ঢোকে।
- `if i >= k - 1:` — প্রথম পূর্ণ window তৈরি হলে তবেই উত্তর লেখা শুরু।
- `while heap[0][1] <= i - k: heappop(heap)` — top-এর index window-এর বাইরে হলে (stale) ঝেড়ে ফেলো; ভেতরের কিছু থাকতে থাকতে থামো।
- `out.append(-heap[0][0])` — এখন top window-এর ভেতরে আর সবচেয়ে বড়; negate করে আসল max।
### Output মিলিয়ে দেখা {#17-output-walkthrough}
`max_sliding_window([9,8,7,6], 2)` section 14-এর dry run মেনে [9,8,7] দেয় — assert pass। main example [3,3,5,5,6,7]; single `[1]` k=1 → [1]; সব-সমান `[4,4,4,4]` → [4,4,4]; negative-mix-এও সঠিক max ধরা পড়ে। প্রতিটা window-এর max একটা নির্দিষ্ট sequence, তাই সরাসরি সমতা assert। সব pass-এর পরে print হয়: `সব test pass!`।
## খরচ ও সাধারণ ভুল {#cost}
### সময় {#18-time-complexity}
**O(n log n)** — প্রতিটা element একবার push আর বড়জোর একবার pop হয় (প্রতিটা O(log n))। কোনো কোনো window-তে একসাথে কয়েকটা stale top purge হলেও amortized মোট pop সংখ্যা O(n)। (monotonic deque এটা O(n)-এ করে; heap version মনে রাখা সহজ।)
### অতিরিক্ত জায়গা {#19-space-complexity}
**O(n)** — worst case (যেমন strictly increasing array) heap-এ প্রায় সব element একসাথে stale-সহ জমে থাকতে পারে। Deque version O(k)-তে রাখে; এটা সরলতার বদলে একটু বেশি memory নেয়।
### যে ভুলগুলো এড়াতে হবে {#20-common-mistakes}
- max-heap না বানিয়ে সরাসরি heapq ব্যবহার — তখন তুমি min track করছ, ভুল উত্তর।
- purge করার সময় ভুল bound (`< i - k` বনাম `<= i - k`) — off-by-one; window-এর ঠিক বাইরের index `i - k`, তাই `<=`।
- window পূর্ণ হওয়ার আগেই answer লেখা শুরু — প্রথম `k-1` index-এ কিছু append করা ভুল।
- purge-এর পর top না পড়ে আগের top পড়া — purge-loop শেষে `heap[0]`-ই current max।
## শেখা ও পরের অনুশীলন {#practice}
### ভিত্তির সঙ্গে সম্পর্ক {#21-which-basic-problem-this-inherits-from}
ভিত্তি `04-stack-and-queue`-এর monotonic deque (একই problem-এর O(n) সমাধান) আর `08`-এর `patterns.md`-র Pattern 5 (Lazy deletion) — "stale entry heap-এ থাকতে দাও, top-এ এলে purge"। heap-এর "শুধু top দেখা যায়" সীমাকে এখানে কাজে লাগানো হলো।
### পরের অনুশীলন {#22-similar-harder-problems}
- Sliding Window Median —