Problem link ও উৎস
- **Original source:** Classic monotonic-deque exercise (chapter centerpiece)
- **Platform:** LeetCode —
- **Topic:** queue (monotonic deque)
- **Difficulty:** Hard
- **Pattern:** monotonic deque
- **Basic idea inherited from:** sliding window basic ([../../02-arrays-and-strings/](../../02-arrays-and-strings/README.md)) + queue — full walkthrough [../patterns.md](../patterns.md) Pattern 5-এ
## প্রশ্ন ও উদাহরণ {#problem}
### সহজ করে প্রশ্ন {#1-problem-in-simple-words}
তোমাকে একটা সংখ্যার array `nums` আর একটা window size `k` দেওয়া আছে। একটা `k`-চওড়া জানালা বাঁ প্রান্ত থেকে ডান প্রান্তে এক ঘর করে slide করো; প্রতিটা অবস্থানে জানালার ভেতরের `k`-টা সংখ্যার **maximum** report করো। শেষে এই maximum গুলোর list ফেরত দাও।
`nums = [1, 3, -1, -3, 5, 3, 6, 7]`, `k = 3`-এর জন্য:
```text
window max
[1 3 -1]-3 5 3 6 7 3
1 [3 -1 -3] 5 3 6 7 3
1 3[-1 -3 5]3 6 7 5
1 3 -1[-3 5 3]6 7 5
1 3 -1 -3 [5 3 6]7 6
1 3 -1 -3 5[3 6 7] 7
answer = [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 -> [3, 3, 5, 5, 6, 7]
Input : nums=[9,8,7,6], k=2 -> [9, 8, 7]
Input : nums=[4,4,4,4], k=2 -> [4, 4, 4]
Edge case 1 (k=1) : [1,5,2], k=1 -> [1,5,2] (প্রতিটা element নিজেই window)
Edge case 2 (k=len) : [1,3,-1], k=3 -> [3] (একটাই window)
Edge case 3 (খালি) : [], k=3 -> []
```
### চেনা উদাহরণে বোঝা {#6-real-life-analogy}
ভাবো deque হলো একটা "ভবিষ্যতের চ্যাম্পিয়ন হতে পারি" দের waiting room, যেখানে লোকেরা শক্তির ক্রমে দাঁড়িয়ে — সামনে সবচেয়ে শক্তিশালী। নতুন একজন শক্তিশালী লোক পেছনের দরজা দিয়ে ঢুকলে, পেছনে দাঁড়ানো যত দুর্বল লোক আছে (তার সমান বা কম শক্তির) সবাইকে সাথে সাথে বের করে দেওয়া হয় — তারা তো আর কখনো জিততে পারবে না, কারণ নতুন লোক তাদের চেয়ে শক্তিশালী আর বেশিদিন থাকবে। আর সামনের লোকের মেয়াদ (window) শেষ হলে তাকে সামনের দরজা দিয়ে বিদায়। তাই room-এর সামনের জনই সবসময় বর্তমান চ্যাম্পিয়ন।
## ভিত্তির ধারণা {#idea}
### আগের কোন ধারণাটি লাগবে {#2-which-basic-idea-does-this-inherit-from}
এটা দুটো জিনিসের মিলন ([../patterns.md](../patterns.md) Pattern 5)। প্রথমত **sliding window basic** ([../../02-arrays-and-strings/](../../02-arrays-and-strings/README.md)) — এক ধাপ করে এগোতে থাকা একটা window। দ্বিতীয়ত **queue** — window-র candidate-রা এক প্রান্তে ঢোকে আর FIFO order-এ অন্য প্রান্তে expire করে। নতুন উপাদানটা হলো *পেছনের* প্রান্ত থেকেও eject করতে দেওয়া — এটাই queue-কে upgrade করে একটা **deque** (double-ended queue)-এ।
### ভেতরের যুক্তি {#3-what-is-the-hidden-math-or-logic}
লুকানো logic হলো একটা **dominance invariant**: deque-তে আমরা শুধু সেই index গুলো রাখি যারা "ভবিষ্যতের কোনো window-র জন্য এখনো max হওয়ার দাবিদার", আর তাদের value গুলো front থেকে back পর্যন্ত **strictly কমতে থাকে** (monotonic decreasing)।
কেন এটা ঠিক রাখা যায়? একটা নতুন value `x` এলে, deque-র যেকোনো element যেটা `x`-এর চেয়ে **ছোট-বা-সমান**, সে আর কোনোদিন কোনো window-র max হতে পারবে না — কারণ `x` একইসাথে **নতুন** (তাই বেশিদিন বাঁচবে) আর **বড়-বা-সমান** (তাই হারাবে না)। তাই তাদের পেছন থেকে ফেলে দেওয়া নিরাপদ। ফলে deque সবসময় decreasing থাকে, আর **front-টাই current window-র max**।
### কী দিয়ে তথ্য রাখব {#4-which-data-structure-is-needed}
একটা **`collections.deque`** যেটা **index** রাখে (value নয়)। index রাখলে দুটো সুবিধা: (১) front কখন window থেকে বেরিয়ে গেছে (expired) সেটা `index <= i - k` দিয়ে ধরা যায়, আর (২) দরকারে `nums[index]` দিয়ে value পাওয়া যায়। deque লাগে কারণ আমাদের **দুই প্রান্তেই** O(1) operation চাই — back-এ push/pop (dominated eject) আর front-এ pop (expired)।
### এটি কেন উপযুক্ত {#5-why-this-data-structure-fits}
সাধারণ list-এ সামনের প্রান্ত থেকে pop O(n) (সব element সরাতে হয়); `deque` দুই প্রান্তেই O(1) দেয়। এখানে দুই ধরনের exit দরকার — back থেকে (নতুন কেউ এসে useless বানালো) আর front থেকে (window পেরিয়ে গেল)। দুটোই O(1) বলে প্রতিটা index জীবনে বড়জোর একবার push আর একবার pop হয় → পুরো কাজ O(n)।
## ধাপে ধাপে সমাধান {#walkthrough}
### প্রথম সরল উপায় {#9-brute-force-thinking}
সবচেয়ে সরল চিন্তা: প্রতিটা window-র জন্য আলাদা করে তার `k`-টা element scan করে max বের করি।
```text
for start in range(len(nums) - k + 1):
answer.append(max(nums[start : start + k]))
```
### কোথায় বেশি কাজ হচ্ছে {#10-why-brute-force-is-slow}
প্রায় `n` টা window, প্রতিটার জন্য `k`-টা element আবার scan → **O(n*k)**। `n = 10^5`, `k = 10^4` হলে এটা প্রায় 10^9 step। একই element বারবার বিভিন্ন window-র scan-এ পড়ে যায় — পুরো অপচয়। আমরা চাই প্রতিটা element-কে বড়জোর একবার push আর একবার pop করে O(n)-তে কাজ সারতে।
### যে বিষয়টি খেয়াল করতে হবে {#11-key-observation}
মূল observation: একটা window-র ভেতরে একটা ছোট element-এর ডান পাশে যদি তার চেয়ে বড় (বা সমান) আর নতুন element থাকে, তবে সেই ছোট element আর কোনোদিন কোনো window-র max হবে না। তাই max খোঁজার জন্য সব element রাখার দরকার নেই — শুধু "এখনো দাবিদার" decreasing chain-টা রাখলেই front-এ উত্তর তৈরি থাকে।
### আরও কম কাজে সমাধান {#12-optimized-intuition}
array-তে একবার বাঁ-থেকে-ডান হাঁটো, index-এর একটা deque রেখে। নতুন `i` এলে: (১) deque-র back থেকে যাদের value `nums[i]`-এর `<=`, তাদের সবাইকে pop করো (useless); (২) `i` push করো back-এ; (৩) front-এর index যদি `i - k`-এর সমান বা ছোট হয় (window পেরিয়ে গেছে), front pop করো; (৪) `i >= k - 1` হলে (প্রথম পূর্ণ window তৈরি) `nums[front]` answer-এ যোগ করো — front-ই max।
### ভাবনার পরিবর্তন {#13-thinking-tweak}
**মোচড়:** "প্রতিটা window নতুন করে scan করব" — এভাবে ভেবো না। ভাবো "আমি একটা ছোট দল রাখব, যেখানে শুধু এখনো-জেতার-সম্ভাবনা-আছে এমন রাই থাকবে, শক্তির ক্রমে সাজানো"। নতুন কেউ এলে দুর্বলদের সাথে সাথে ছাঁটো; মেয়াদ ফুরালে সামনের জনকে বিদায়। তখন max খুঁজতে কখনোই scan করতে হয় না — সবসময় front-এ তৈরি।
### ছবিতে বোঝা {#7-visual-explanation}
`[1, 3, -1, -3, 5, 3, 6, 7]`, `k = 3`-এর জন্য deque-তে (index রাখা, তবে নিচে value দেখানো; front বাঁয়ে) কী ঘটে:
```text
i val deque after step (values) window max (front)
0 1 [1] — —
1 3 [3] (1 ejected: <=3) — —
2 -1 [3,-1] [1, 3,-1] 3
3 -3 [3,-1,-3] [3,-1,-3] 3
4 5 [5] (front 3 expired; -3,-1 ejected)
[-1,-3, 5] 5
5 3 [5,3] [-3, 5, 3] 5
6 6 [6] (3 and 5 ejected) [5, 3, 6] 6
7 7 [7] (6 ejected) [3, 6, 7] 7
answer: [3, 3, 5, 5, 6, 7]
```
(একই trace [../patterns.md](../patterns.md) Pattern 5-এ আছে।)
### ছোট input-এ ধাপে ধাপে {#14-step-by-step-dry-run}
Input `nums = [9, 8, 7, 6]`, `k = 2`:
1. `i=0 (9)`: deque খালি, push → `[0]`। front `0 <= 0-2`? না। `i >= 1`? না।
2. `i=1 (8)`: `nums[0]=9 <= 8`? না, push → `[0,1]`। front `0 <= -1`? না। `i>=1`: answer += `nums[0]=9` → `[9]`
3. `i=2 (7)`: `nums[1]=8 <= 7`? না, push → `[0,1,2]`। front `0 <= 0`? হ্যাঁ → popleft → `[1,2]`। answer += `nums[1]=8` → `[9,8]`
4. `i=3 (6)`: `nums[2]=7 <= 6`? না, push → `[1,2,3]`। front `1 <= 1`? হ্যাঁ → popleft → `[2,3]`। answer += `nums[2]=7` → `[9,8,7]`
5. return `[9, 8, 7]`
## কোড ও ব্যাখ্যা {#code}
### Python {#15-python-solution}
```python
from collections import deque
def max_sliding_window(nums, k):
if not nums or k == 0:
return []
dq = deque() # index রাখে; value front->back এ কমতে থাকে
result = []
for i, x in enumerate(nums):
while dq and nums[dq[-1]] <= x: # x-এর <= back-রা চিরতরে useless
dq.pop()
dq.append(i) # x নিজে এখন দাবিদার
if dq[0] <= i - k: # front window থেকে বেরিয়ে গেছে
dq.popleft()
if i >= k - 1: # প্রথম পূর্ণ window থেকে answer নেওয়া শুরু
result.append(nums[dq[0]]) # front-টাই current window-র max
return result
# ---- tests ----
assert max_sliding_window([1, 3, -1, -3, 5, 3, 6, 7], 3) == [3, 3, 5, 5, 6, 7]
assert max_sliding_window([9, 8, 7, 6], 2) == [9, 8, 7]
assert max_sliding_window([4, 4, 4, 4], 2) == [4, 4, 4] # সমান value-ও ঠিক
assert max_sliding_window([1, 5, 2], 1) == [1, 5, 2] # k=1
assert max_sliding_window([1, 3, -1], 3) == [3] # k=len
assert max_sliding_window([], 3) == [] # খালি
print("সব test pass!")
```
### কোডের প্রতিটি অংশ {#16-line-by-line-code-explanation}
- `if not nums or k == 0: return []` — খালি input বা k=0-এ কিছু করার নেই।
- `dq = deque()` — index জমবে, value নয়; index থাকলে expiry আর value দুটোই পাওয়া যায়।
- `while dq and nums[dq[-1]] <= x:` / `dq.pop()` — নতুন `x`-এর `<=` সব back-element চিরতরে useless, পেছন থেকে ফেলে দাও (`<=` বলে সমান value-ও সরে, তাতে front সবসময় সাম্প্রতিকতমটা থাকে)।
- `dq.append(i)` — `x` এখন একজন দাবিদার, back-এ যোগ।
- `if dq[0] <= i - k: dq.popleft()` — front-এর index যদি window-র বাঁ সীমার বাইরে পড়ে যায়, সামনের দরজা দিয়ে বিদায়। (প্রতি step-এ বড়জোর একজনই expire করে, তাই `if`-ই যথেষ্ট, `while` লাগে না।)
- `if i >= k - 1: result.append(nums[dq[0]])` — index `k-1` থেকে প্রতিটা পূর্ণ window-র জন্য front-এর value-ই max।
### Output মিলিয়ে দেখা {#17-output-walkthrough}
`max_sliding_window([1,3,-1,-3,5,3,6,7], 3)` → section 7-এর trace মতো প্রতিটা window-র max `[3,3,5,5,6,7]`। `max_sliding_window([4,4,4,4], 2)` → `<=` comparison-এর কারণে পুরোনো সমান `4`-গুলো eject হয়ে front-এ সবসময় সাম্প্রতিকতম `4` থাকে, ফল `[4,4,4]`। সব assert pass করে শেষে print: `সব test pass!`।
## খরচ ও সাধারণ ভুল {#cost}
### সময় {#18-time-complexity}
**O(n)** — প্রতিটা index ঠিক একবার deque-তে push হয় আর বড়জোর একবার pop হয় (back থেকে beaten হয়ে, বা front থেকে expired হয়ে)। মোট deque operation ≤ 2n, যেকোনো step যতগুলো ejection ঘটাক না কেন। Naive O(n*k)-র তুলনায় বিশাল লাভ।
### অতিরিক্ত জায়গা {#19-space-complexity}
**O(k)** — deque-তে একসাথে বড়জোর `k`-টা index থাকতে পারে (একটা window-র সমান), কারণ পুরোনোরা expire হয়ে যায়। output list আলাদা করে ধরা হয় না।
### যে ভুলগুলো এড়াতে হবে {#20-common-mistakes}
- deque-তে value রাখা, index নয় — তখন front কখন expire করল সেটা ধরা যায় না।
- `<` বনাম `<=` — back eject-এ `<=` দরকার যাতে সমান value-র পুরোনোটা সরে; `<` দিলে duplicate জমে front পুরোনো index ধরে রাখতে পারে।
- expiry check করতে `while` ব্যবহার করা ভুল নয়, কিন্তু `if`-ই যথেষ্ট — প্রতি step-এ বড়জোর একজন front-element expire করে।
- `i >= k - 1` শর্ত ভুলে গিয়ে অসম্পূর্ণ প্রথম window-গুলোর জন্যও answer যোগ করা।
## শেখা ও পরের অনুশীলন {#practice}
### ভিত্তির সঙ্গে সম্পর্ক {#21-which-basic-problem-this-inherits-from}
ভিত্তি: sliding window basic ([../../02-arrays-and-strings/](../../02-arrays-and-strings/README.md)) + queue, একসাথে monotonic deque-তে রূপান্তরিত — [../patterns.md](../patterns.md) Pattern 5 (chapter-এর required centerpiece)। dominance idea-টা Pattern 4 (monotonic stack)-এর জ্ঞাতি; পার্থক্য শুধু এখানে element front থেকেও (expire হয়ে) বেরোয়।
### পরের অনুশীলন {#22-similar-harder-problems}
- Shortest Subarray with Sum at Least K (prefix sum-এর উপর monotonic deque) —