Problem link ও উৎস
- **Original source:** Classic monotonic-deque exercise
- **Platform:** LeetCode —
- **Topic:** array / monotonic deque
- **Difficulty:** Hard
- **Pattern:** monotonic deque (descending)
- **Basic idea inherited from:** sliding window + queue — পূর্ণ walkthrough [../../04-stack-and-queue/patterns.md](../../04-stack-and-queue/patterns.md)-তে
## প্রশ্ন ও উদাহরণ {#problem}
### সহজ করে প্রশ্ন {#1-problem-in-simple-words}
একটা array `nums` আর একটা সংখ্যা `k` দেওয়া। একটা `k`-আকারের window বাঁ থেকে ডানে এক ঘর করে সরছে। প্রতিটা window-অবস্থানে সেই window-এর **সর্বোচ্চ** মান বের করো, আর সব window-এর সর্বোচ্চগুলো ক্রমে একটা list-এ ফেরত দাও।
```text
nums = [1,3,-1,-3,5,3,6,7], k = 3
windows: [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]
```
### 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,11], k = 2 -> [11]
Edge case 1 (k = 1): [1,-1], k=1 -> [1,-1] (প্রতিটা একাই window)
Edge case 2 (খালি): [], k=3 -> []
```
### চেনা উদাহরণে বোঝা {#6-real-life-analogy}
ভাবো একসারি লোক উচ্চতা নিয়ে দাঁড়িয়ে, তুমি সামনে থেকে দেখছ। নতুন কেউ পেছনে এসে দাঁড়ালে, তার সামনের যারা তার চেয়ে বেঁটে, তারা আর "সবচেয়ে লম্বা" হওয়ার দৌড়ে নেই — কারণ এই নতুন লম্বা জন যতক্ষণ আছে, ততক্ষণ তাদের ছাপিয়ে যাবে। তাই বেঁটেদের সারি থেকে সরিয়ে দাও। সারির একদম সামনে সবসময় এই মুহূর্তের সবচেয়ে লম্বা জন।
## ভিত্তির ধারণা {#idea}
### আগের কোন ধারণাটি লাগবে {#2-which-basic-idea-does-this-inherit-from}
ভিত **sliding window** (problem 10) আর **queue** (FIFO)। সাধারণ window-এ প্রতিবার max খুঁজতে গেলে O(k) লাগে; এখানে চালাকি হলো একটা **monotonic deque** (দুই দিকে খোলা queue) রাখা, যেখানে শুধু "ভবিষ্যতে কাজে লাগতে পারে এমন candidate"-রা descending order-এ থাকে। queue + sliding window-এর পূর্ণ গল্প [../../04-stack-and-queue/patterns.md](../../04-stack-and-queue/patterns.md)-তে — এই problem সেই অধ্যায়ে hand-off করে।
### ভেতরের যুক্তি {#3-what-is-the-hidden-math-or-logic}
লুকানো logic একটা domination নিয়ম: window-এ যদি কোনো নতুন element `x` আসে আর তার বাঁয়ে এমন কেউ থাকে যে `x`-এর চেয়ে **ছোট-বা-সমান**, তবে সেই ছোট জনের আর কোনো ভবিষ্যৎ নেই — যতক্ষণ সে window-এ থাকবে, `x`-ও থাকবে এবং বড়। তাই তাকে চিরতরে বাদ দেওয়া যায়। ফলে deque সবসময় **strictly descending** থাকে, আর তার সামনে (front) থাকে চলতি window-এর সর্বোচ্চ।
### কী দিয়ে তথ্য রাখব {#4-which-data-structure-is-needed}
একটা **deque** (`collections.deque`), যা element-এর **index** রাখে (মান নয়, যাতে কে window থেকে বেরিয়ে গেছে তা index দিয়ে বোঝা যায়)। deque-এর index-গুলোর মানগুলো সামনে-থেকে-পেছনে descending। সাথে output list।
### এটি কেন উপযুক্ত {#5-why-this-data-structure-fits}
দুই দিকে কাজ লাগে: **পেছনে (back)** ছোট candidate বাদ দিতে হয় (নতুন বড় element এলে), আর **সামনে (front)** থেকে window-ছাড়া পুরোনো index বাদ দিতে হয়। deque দুই প্রান্তেই O(1) push/pop দেয় — তাই দুটো কাজই দ্রুত। index রাখায় "front-এর element কি এখনো window-এ?" তা `front <= i-k` দিয়ে যাচাই করা যায়।
## ধাপে ধাপে সমাধান {#walkthrough}
### প্রথম সরল উপায় {#9-brute-force-thinking}
প্রথম সরল চিন্তা: প্রতিটা window-অবস্থানের জন্য সেই `k`-টা element-এর মধ্যে `max()` আলাদা করে বের করো।
```text
res = []
for i in range(n - k + 1):
res.append(max(nums[i : i + k]))
```
### কোথায় বেশি কাজ হচ্ছে {#10-why-brute-force-is-slow}
প্রতিটা window-এ আবার `k`-টা element scan করে max — মোট **O(n·k)**। `k` বড় হলে অসহনীয় ধীর, আর প্রতিবার আগের window-এর কাজ ফেলে দিয়ে নতুন করে গোনা হচ্ছে। monotonic deque সেই কাজ পুনর্ব্যবহার করে: প্রতিটা index ঠিক একবার ঢোকে, একবার বের হয় → O(n)।
### যে বিষয়টি খেয়াল করতে হবে {#11-key-observation}
মূল observation: একটা element যদি তার ডানে আসা কোনো element-এর চেয়ে ছোট-বা-সমান হয়, তবে সে আর কখনো window-max হতে পারবে না (ডানের বড়জন তাকে সবসময় ছাপাবে যতক্ষণ দুজনই window-এ)। তাই এমন "ছাপিয়ে যাওয়া" candidate-দের রাখার দরকার নেই — deque-কে descending রাখলে front-ই max।
### আরও কম কাজে সমাধান {#12-optimized-intuition}
প্রতিটা index `i` (মান `x`)-এ:
- **পেছন পরিষ্কার:** deque-এর শেষের index-গুলোর মান `<= x` হলে pop (তারা আর দরকারি নয়); তারপর `i` push।
- **সামনে পরিষ্কার:** front index যদি window ছেড়ে গেছে (`front == i - k`), তবে popleft।
- **উত্তর:** `i >= k-1` হলে window পূর্ণ — front-এর মানই (`nums[deque[0]]`) এই window-এর max, output-এ রাখো।
প্রতিটা index একবার push, একবার pop → মোট O(n)।
### ভাবনার পরিবর্তন {#13-thinking-tweak}
**মোচড়:** "প্রতিটা window-এ max আবার খুঁজব" (O(n·k)) ভোলো। ভাবো "একটা candidate-সারি রাখব, যেখান থেকে নিশ্চিত-হেরে-যাওয়া (ছোট) লোকদের ছেঁটে ফেলি; তাহলে সারির সামনেই সবসময় বর্তমান max।" max খোঁজা গায়েব হয়ে একটা O(1) "front দেখা"-তে নেমে আসে।
### ছবিতে বোঝা {#7-visual-explanation}
`nums = [1,3,-1,-3,5,3,6,7], k = 3` — deque-এ index (মান descending), front = window max:
```text
i=0 v=1 : deque idx[0] (মান 1)
i=1 v=3 : 1<=3 পেছন pop; deque idx[1] (মান 3)
i=2 v=-1: deque idx[1,2] -> window পূর্ণ, max=nums[1]=3
i=3 v=-3: deque idx[1,2,3]; front 1==3-3 বাইরে? না(=0?) -> max=nums[1]=3
i=4 v=5 : -3,-1,3 সব<=5 pop; deque idx[4]; max=nums[4]=5
i=5 v=3 : deque idx[4,5]; max=nums[4]=5
i=6 v=6 : 3,5<=6 pop; deque idx[6]; max=nums[6]=6
i=7 v=7 : 6<=7 pop; deque idx[7]; max=nums[7]=7
ফল: [3,3,5,5,6,7]
```
### ছোট input-এ ধাপে ধাপে {#14-step-by-step-dry-run}
Input `nums = [9, 11], k = 2`:
1. `i=0 x=9`: deque খালি → push 0 → `deque=[0]`। front `0 == 0-2`? না। `i >= k-1`(0>=1)? না।
2. `i=1 x=11`: পেছন `nums[0]=9 <= 11` → pop; push 1 → `deque=[1]`। front `1 == 1-2`? না। `i>=1`? হ্যাঁ → `res.append(nums[1]=11)`।
3. শেষ। ফল: `[11]`।
## কোড ও ব্যাখ্যা {#code}
### Python {#15-python-solution}
```python
from collections import deque
def max_sliding_window(nums, k):
if not nums:
return []
dq = deque() # index রাখে; মানগুলো descending
result = []
for i, x in enumerate(nums):
while dq and nums[dq[-1]] <= x:
dq.pop() # ছোট candidate চিরতরে বাদ
dq.append(i)
if dq[0] == i - k: # front window ছেড়ে গেছে
dq.popleft()
if i >= k - 1: # window পূর্ণ -> front = max
result.append(nums[dq[0]])
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, 11], 2) == [11]
assert max_sliding_window([1, -1], 1) == [1, -1] # k = 1
assert max_sliding_window([], 3) == [] # খালি
print("সব test pass!")
```
### কোডের প্রতিটি অংশ {#16-line-by-line-code-explanation}
- `if not nums: return []` — খালি input-এ কোনো window নেই।
- `dq = deque()` — index-এর monotonic (descending-মান) queue।
- `while dq and nums[dq[-1]] <= x: dq.pop()` — নতুন `x`-এর চেয়ে ছোট-সমান পেছনের candidate-রা চিরতরে অপ্রয়োজনীয়, বাদ।
- `dq.append(i)` — নতুন index পেছনে যোগ।
- `if dq[0] == i - k: dq.popleft()` — front-এর index window-এর বাঁ সীমা পেরিয়ে গেলে সামনে থেকে বাদ।
- `if i >= k - 1: result.append(nums[dq[0]])` — প্রথম পূর্ণ window থেকে শুরু করে প্রতিবার front-এর মান (= current max) রাখি।
- `return result` — প্রতিটা window-এর max-এর list।
### Output মিলিয়ে দেখা {#17-output-walkthrough}
`[1,3,-1,-3,5,3,6,7], k=3` → deque front ধরে রাখে চলতি max; ছোটরা বাদ পড়ে, পুরোনো index window ছাড়লে front থেকে যায় → `[3,3,5,5,6,7]`, assert pass। `[9,11], k=2` → `[11]`; `[1,-1], k=1` → প্রতিটা একাই window → `[1,-1]`; `[], k=3` → `[]`। শেষে print: `সব test pass!`।
### JavaScript ও test cases {#25-javascript-solution-with-test-cases}
index-এর monotonic deque (descending মান) — array দিয়ে দুই প্রান্তে push/pop।
```javascript
const assert = (cond, msg = "") => { if (!cond) throw new Error("FAIL " + msg); };
const eq = (a, b) => JSON.stringify(a) === JSON.stringify(b);
// max of each k-sized sliding window (monotonic deque of indices)
function maxSlidingWindow(nums, k) {
if (nums.length === 0) return [];
const dq = []; // index রাখে; মানগুলো descending
const result = [];
for (let i = 0; i < nums.length; i++) {
while (dq.length && nums[dq[dq.length - 1]] <= nums[i]) dq.pop(); // ছোট বাদ
dq.push(i);
if (dq[0] === i - k) dq.shift(); // front window ছেড়ে গেছে
if (i >= k - 1) result.push(nums[dq[0]]); // window পূর্ণ -> front = max
}
return result;
}
// ---- test cases (example + edge) ----
assert(eq(maxSlidingWindow([1, 3, -1, -3, 5, 3, 6, 7], 3), [3, 3, 5, 5, 6, 7]), "classic");
assert(eq(maxSlidingWindow([9, 11], 2), [11]), "two");
assert(eq(maxSlidingWindow([1, -1], 1), [1, -1]), "k=1"); // edge
assert(eq(maxSlidingWindow([], 3), []), "empty"); // edge
console.log("সব JS test pass!");
```
> **JS টীকা:** deque হিসেবে সাধারণ array — পেছনে `push`/`pop`, সামনে `shift` (front-pop)। অবশ্যই **index** রাখো, মান নয় — তাহলেই `dq[0] === i - k` দিয়ে front window ছেড়েছে কিনা বোঝা যায়। array compare-এ `JSON.stringify`।
### TypeScript ও test cases {#26-typescript-solution-with-test-cases}
```typescript
function maxSlidingWindow(nums: number[], k: number): number[] {
if (nums.length === 0) return [];
const dq: number[] = []; // indices, values descending
const result: number[] = [];
for (let i = 0; i < nums.length; i++) {
while (dq.length && nums[dq[dq.length - 1]] <= nums[i]) dq.pop();
dq.push(i);
if (dq[0] === i - k) dq.shift();
if (i >= k - 1) result.push(nums[dq[0]]);
}
return result;
}
function expectArr(actual: number[], exp: number[], msg = ""): void {
if (JSON.stringify(actual) !== JSON.stringify(exp))
throw new Error(`FAIL ${msg}: got ${JSON.stringify(actual)}`);
}
expectArr(maxSlidingWindow([1, 3, -1, -3, 5, 3, 6, 7], 3), [3, 3, 5, 5, 6, 7], "classic");
expectArr(maxSlidingWindow([1, -1], 1), [1, -1], "k=1");
expectArr(maxSlidingWindow([], 3), [], "empty");
console.log("সব TS test pass!");
```
> **TS টীকা:** `dq: number[]` declare করায় deque-তে শুধু index (number) ঢোকে; `nums[dq[...]]` access-ও number, তাই domination compare টাইপে নিশ্চিত — মান বনাম index গুলিয়ে ফেলার bug আটকায়।
## খরচ ও সাধারণ ভুল {#cost}
### সময় {#18-time-complexity}
**O(n)** — প্রতিটা index ঠিক একবার deque-এ ঢোকে আর বড়জোর একবার বের হয়; তাই সব push/pop মিলিয়ে মোট কাজ linear, `k`-নিরপেক্ষ।
### অতিরিক্ত জায়গা {#19-space-complexity}
**O(k)** — deque-এ একসাথে বড়জোর `k`-টা index থাকে (output আলাদা ধরলে)।
### যে ভুলগুলো এড়াতে হবে {#20-common-mistakes}
- deque-এ মান রাখা, index নয় — তখন front window ছেড়েছে কিনা (`== i-k`) বোঝা যায় না।
- পেছনে pop-এ `<` ব্যবহার করে সমান মান রেখে দেওয়া — কাজ করে, কিন্তু `<=` রাখলে duplicate কম, পরিষ্কার; তবে সমান হলে দুটোই রাখলেও উত্তর ঠিক, শুধু front-pop সাবধানে।
- `i >= k-1` শর্ত ভুলে শুরুর অসম্পূর্ণ window-গুলোতেও output দেওয়া।
- front-pop শর্ত `dq[0] < i-k+1`-এর বদলে ভুল সীমা দেওয়া — window range `[i-k+1 .. i]`, তাই `dq[0] == i-k` মানে ঠিক বাঁ-সীমার এক ঘর বাইরে।
## শেখা ও পরের অনুশীলন {#practice}
### ভিত্তির সঙ্গে সম্পর্ক {#21-which-basic-problem-this-inherits-from}
ভিত্তি: sliding window (Longest Unique Substring #10)-এর "প্রতিটা index একবার ঢোকে-বেরোয়" + queue-এর FIFO/দুই-প্রান্ত operation। পূর্ণ deque-গল্প [../../04-stack-and-queue/patterns.md](../../04-stack-and-queue/patterns.md)-তে; chapter-এর [../patterns.md](../patterns.md)-এর "Pattern 2 — Sliding Window"-এর এটাই hard শিখর, যা stack/queue অধ্যায়ে hand-off করে।
### পরের অনুশীলন {#22-similar-harder-problems}
- Sliding Window Minimum (একই deque, ascending) — দেখো [../../04-stack-and-queue/patterns.md](../../04-stack-and-queue/patterns.md)
- Shortest Subarray with Sum at Least K (deque + prefix sum) —