Problem link ও উৎস
- **Original source:** Classic monotonic-stack exercise
- **Platform:** LeetCode —
- **Topic:** stack (monotonic)
- **Difficulty:** Medium
- **Pattern:** monotonic stack — next greater, distance flavor
- **Basic idea inherited from:** Problem 7 (next greater element) — তবে এবার value-র বদলে *distance* (কত দিন পরে গরম পড়বে) চাই
## প্রশ্ন ও উদাহরণ {#problem}
### সহজ করে প্রশ্ন {#1-problem-in-simple-words}
তোমাকে প্রতিদিনের temperature-এর একটা list দেওয়া আছে। প্রতিটা দিনের জন্য বলতে হবে — আজকের চেয়ে কড়া গরম একটা দিন পেতে আর **কত দিন** অপেক্ষা করতে হবে। ভবিষ্যতে এমন কোনো গরম দিন না থাকলে সেই দিনের উত্তর `0`।
মানে আউটপুটটা ঠিক ইনপুটের সমান লম্বা একটা list, যেখানে প্রতিটা ঘর "কয় দিন পরে" সেই সংখ্যাটা ধরে রাখে।
```text
temperatures : [73, 74, 75, 71, 69, 72, 76, 73]
answer : [ 1, 1, 4, 2, 1, 1, 0, 0]
```
### Input ও output {#8-example-input-and-output}
```text
Input : [73,74,75,71,69,72,76,73] -> Output: [1,1,4,2,1,1,0,0]
Input : [30,40,50,60] -> Output: [1,1,1,0]
Input : [30,60,90] -> Output: [1,1,0]
Edge case 1 (সব কমছে) : [90,80,70] -> [0,0,0] (কেউ কখনো গরম দিন পায় না)
Edge case 2 (একটা দিন) : [50] -> [0]
Edge case 3 (খালি list) : [] -> []
```
### চেনা উদাহরণে বোঝা {#6-real-life-analogy}
ভাবো একটা সারিতে কয়েকজন মানুষ লাইন ধরে দাঁড়িয়ে আছে, প্রত্যেকের হাতে একটা ছোট পতাকা যাতে তাদের temperature লেখা। যতক্ষণ পরের লোকটা ঠান্ডা, ততক্ষণ আগের লোকেরা "আমার গরম দিন কই" বলে অপেক্ষায় দাঁড়িয়ে থাকে (stack-এ জমে)। হঠাৎ একজন কড়া-গরম লোক এসে দাঁড়ালে, পেছনে অপেক্ষায় থাকা সব ঠান্ডা লোক একসাথে হাত নামিয়ে বলে "পেয়েছি!" — আর তাদের কত দিন অপেক্ষা করতে হলো, সেটা গোনা হয়ে যায়।
## ভিত্তির ধারণা {#idea}
### আগের কোন ধারণাটি লাগবে {#2-which-basic-idea-does-this-inherit-from}
এটা সরাসরি **Problem 7 — Next Greater Element**-এর বড় ভাই। সেখানে তুমি প্রতিটা element-এর ডানদিকের প্রথম strictly বড় value খুঁজছিলে; এখানেও ঠিক তাই, কিন্তু value-টা নয় — চাই তার থেকে **কত index দূরে** সেই বড় দিনটা। তাই answer-এ value বসানোর বদলে আমরা index-এর পার্থক্য বসাই।
এক কথায়: same monotonic-stack machinery, শুধু শেষ মুহূর্তে `i - j` লিখি `nums[i]` লেখার বদলে।
### ভেতরের যুক্তি {#3-what-is-the-hidden-math-or-logic}
লুকানো logic হলো একটা **invariant**: stack-এ আমরা শুধু সেই দিনগুলোর index রাখি যারা এখনো নিজেদের "গরম দিন" খুঁজে পায়নি, আর তাদের temperature গুলো নিচ থেকে উপর পর্যন্ত **strictly কমতে থাকে** (monotonic decreasing)।
এই invariant-টাই correctness দেয়: নতুন একটা দিন `i` যখন আসে, সে stack-এর top থেকে শুরু করে নিজের চেয়ে ছোট সব দিনকে "এই তো তোমার গরম দিন" বলে resolve করে দেয় — কারণ stack ছোট-উপরে রাখা বলে, top থেকে যতগুলো `i`-এর চেয়ে ঠান্ডা, তারা সবাই `i`-কেই তাদের প্রথম গরম দিন হিসেবে পায়।
### কী দিয়ে তথ্য রাখব {#4-which-data-structure-is-needed}
একটা **stack** যেখানে আমরা temperature নয়, **index** রাখি (`Python`-এ সাধারণ `list`)। index রাখলেই দূরত্ব `i - j` বের করা যায়। সাথে একটা `answer` list যেটা শুরুতে সব `0` দিয়ে ভরা থাকে — যে দিন কখনো গরম দিন পায় না, তার জন্য `0` এমনিতেই বসে থাকবে।
### এটি কেন উপযুক্ত {#5-why-this-data-structure-fits}
"প্রথম গরম দিন" মানে "সবচেয়ে কাছের ভবিষ্যতের বড় value" — আর এটা monotonic stack-এর হুবহু খেলার মাঠ। প্রতিটা দিন stack-এ একবার ঢোকে আর বড়জোর একবার বের হয়, তাই push/pop দুটোই amortized O(1)। index রাখায় দূরত্ব O(1)-তে পাওয়া যায়, আর strictly-decreasing রাখার কারণে নতুন দিন এসে শুধু তাদেরই pop করে যাদের answer সে নিজেই।
## ধাপে ধাপে সমাধান {#walkthrough}
### প্রথম সরল উপায় {#9-brute-force-thinking}
সবচেয়ে সরল চিন্তা: প্রতিটা দিন `i`-এর জন্য তার ডানদিকে একটা একটা করে দিন `j` ঘুরে দেখি, প্রথম যেখানে `temp[j] > temp[i]` সেখানে থেমে `j - i` লিখি; না পেলে `0`।
```text
day i -> j = i+1, i+2, ... খুঁজতে থাকো প্রথম strictly বড় temperature
পেলে answer[i] = j - i; নাহলে answer[i] = 0
```
### কোথায় বেশি কাজ হচ্ছে {#10-why-brute-force-is-slow}
প্রতিটা দিনের জন্য সবচেয়ে খারাপ ক্ষেত্রে list-এর শেষ পর্যন্ত হাঁটতে হয়। যেমন `[80, 79, 78, ..., 1, 100]`-এর মতো লম্বা নামতে-থাকা list-এ প্রতিটা দিন প্রায় পুরো বাকি অংশ scan করে → **O(n^2)**। একই দিন বারবার অন্যদের scan-এ পড়ে যায়, যা পুরো অপচয়। আমরা চাই প্রতিটা দিনকে বড়জোর একবার করে ছোঁয়া — O(n)।
### যে বিষয়টি খেয়াল করতে হবে {#11-key-observation}
মূল observation: একটা গরম দিন `i` যখন আসে, সে নিজের চেয়ে ঠান্ডা সব **এখনো-অপেক্ষমাণ** দিনের answer একসাথে দিয়ে দিতে পারে। আর "এখনো অপেক্ষমাণ আর ঠান্ডা" দিনগুলো ঠিক stack-এর top-এ পরপর সাজানো থাকে (strictly decreasing)। তাই সামনে খোঁজার বদলে, নতুন দিনকে দিয়ে পেছনের দিনদের answer **deliver** করাও।
### আরও কম কাজে সমাধান {#12-optimized-intuition}
list-এ একবার বাঁ থেকে ডানে হাঁটো, index-এর একটা stack রেখে। নতুন দিন `i` এলে: যতক্ষণ stack খালি নয় আর top-এর দিনের temperature `temp[i]`-এর চেয়ে ছোট, ততক্ষণ pop করো আর pop-করা দিন `j`-এর জন্য `answer[j] = i - j` বসাও। এরপর `i`-কে stack-এ push করো (এখনো তার নিজের গরম দিন বাকি)। শেষে stack-এ যারা পড়ে থাকে তাদের answer `0`-ই থেকে যায়।
### ভাবনার পরিবর্তন {#13-thinking-tweak}
**মোচড়:** প্রশ্নটা উল্টে দাও। "আমার গরম দিন কোথায়" — এভাবে প্রত্যেকটা দিনকে সামনে খুঁজতে পাঠানোর বদলে, প্রতিটা নতুন দিনকে জিজ্ঞেস করো "আমি এসে কাদের অপেক্ষা শেষ করলাম?" answer push নয়, **deliver** করা হয় — এই উল্টো দৃষ্টিতেই O(n^2) থেকে O(n)-এ নামা।
### ছবিতে বোঝা {#7-visual-explanation}
`[73, 74, 75, 71, 69, 72, 76, 73]`-এর জন্য stack-এ (index রাখা, top ডানে) কী ঘটে দেখি:
```text
i temp action stack(idx) answer-update
0 73 কেউ নেই -> wait [0] —
1 74 temp[0]=73<74 -> pop 0, ans[0]=1-0=1 [1] ans[0]=1
2 75 temp[1]=74<75 -> pop 1, ans[1]=2-1=1 [2] ans[1]=1
3 71 temp[2]=75<71? না -> wait [2,3] —
4 69 temp[3]=71<69? না -> wait [2,3,4] —
5 72 temp[4]=69<72 -> pop 4, ans[4]=5-4=1
temp[3]=71<72 -> pop 3, ans[3]=5-3=2
temp[2]=75<72? না -> wait [2,5] ans[4]=1, ans[3]=2
6 76 temp[5]=72<76 -> pop 5, ans[5]=6-5=1
temp[2]=75<76 -> pop 2, ans[2]=6-2=4 [6] ans[5]=1, ans[2]=4
7 73 temp[6]=76<73? না -> wait [6,7] —
end stack-এ পড়ে থাকা 6,7 কখনো গরম দিন পায়নি -> ans=0
```
### ছোট input-এ ধাপে ধাপে {#14-step-by-step-dry-run}
Input `[30, 60, 90]`:
1. শুরু: `stack = []`, `answer = [0, 0, 0]`
2. `i=0, temp=30` — stack খালি, push → `stack = [0]`
3. `i=1, temp=60` — top index 0-র temp 30 < 60, pop 0, `answer[0] = 1 - 0 = 1`; stack খালি, push 1 → `stack = [1]`, `answer = [1,0,0]`
4. `i=2, temp=90` — top index 1-র temp 60 < 90, pop 1, `answer[1] = 2 - 1 = 1`; push 2 → `stack = [2]`, `answer = [1,1,0]`
5. list শেষ, stack-এ index 2 পড়ে আছে — তার answer `0`-ই থাকে → return `[1, 1, 0]`
## কোড ও ব্যাখ্যা {#code}
### Python {#15-python-solution}
```python
def daily_temperatures(temperatures):
n = len(temperatures)
answer = [0] * n
stack = [] # index দের stack, temp decreasing
for i, temp in enumerate(temperatures):
while stack and temperatures[stack[-1]] < temp:
j = stack.pop() # j-এর গরম দিন আজকেই
answer[j] = i - j # value নয়, distance
stack.append(i) # i নিজের গরম দিনের অপেক্ষায়
return answer # stack-এ যারা থাকে, তাদের 0-ই থাকে
# ---- tests ----
assert daily_temperatures([73, 74, 75, 71, 69, 72, 76, 73]) == [1, 1, 4, 2, 1, 1, 0, 0]
assert daily_temperatures([30, 40, 50, 60]) == [1, 1, 1, 0]
assert daily_temperatures([30, 60, 90]) == [1, 1, 0]
assert daily_temperatures([90, 80, 70]) == [0, 0, 0] # সব কমছে
assert daily_temperatures([50]) == [0] # একটা দিন
assert daily_temperatures([]) == [] # খালি list
print("সব test pass!")
```
### কোডের প্রতিটি অংশ {#16-line-by-line-code-explanation}
- `answer = [0] * n` — শুরুতেই সব `0`; যে দিন কখনো গরম দিন পায় না, তার জন্য কিছুই করতে হবে না।
- `stack = []` — এখানে index জমবে, temperature নয়; দূরত্ব মাপার জন্য index দরকার।
- `while stack and temperatures[stack[-1]] < temp:` — top-এর দিন আজকের চেয়ে ঠান্ডা হলে তার গরম দিন আজকেই পাওয়া গেল।
- `j = stack.pop()` / `answer[j] = i - j` — pop করা দিন `j`-এর answer = কত index দূরে আজ, মানে `i - j`।
- `stack.append(i)` — আজকের দিন এখনো নিজের গরম দিন পায়নি, তাই অপেক্ষায় বসুক।
- `return answer` — loop শেষে stack-এ পড়ে থাকা দিনগুলোর answer `0`-ই থাকে।
### Output মিলিয়ে দেখা {#17-output-walkthrough}
`daily_temperatures([73,74,75,71,69,72,76,73])` → section 7-এর trace মতো index 6 আর 7 ছাড়া সবাই গরম দিন পায়, ফল `[1,1,4,2,1,1,0,0]`। `daily_temperatures([90,80,70])` → কোনো দিন পরের কোনো বড় temperature পায় না, তাই pop-ই হয় না, সব `0`। সব assert pass করে শেষে print: `সব test pass!`।
### JavaScript ও test cases {#25-javascript-solution-with-test-cases}
```javascript
const assert = (cond, msg = "") => { if (!cond) throw new Error("FAIL " + msg); };
function dailyTemperatures(temperatures) {
const n = temperatures.length;
const answer = new Array(n).fill(0); // না-পাওয়া দিনের answer 0-ই থাকে
const stack = []; // index রাখে, temp decreasing
for (let i = 0; i < n; i++) {
while (stack.length && temperatures[stack[stack.length - 1]] < temperatures[i]) {
const j = stack.pop(); // j-এর গরম দিন আজকেই
answer[j] = i - j; // value নয়, distance
}
stack.push(i); // i নিজের গরম দিনের অপেক্ষায়
}
return answer;
}
// ---- test cases ----
const eq = (a, b) => JSON.stringify(a) === JSON.stringify(b);
assert(eq(dailyTemperatures([73, 74, 75, 71, 69, 72, 76, 73]), [1, 1, 4, 2, 1, 1, 0, 0]), "main");
assert(eq(dailyTemperatures([30, 40, 50, 60]), [1, 1, 1, 0]), "increasing");
assert(eq(dailyTemperatures([30, 60, 90]), [1, 1, 0]), "small");
assert(eq(dailyTemperatures([90, 80, 70]), [0, 0, 0]), "সব কমছে");
assert(eq(dailyTemperatures([50]), [0]), "একটা দিন");
assert(eq(dailyTemperatures([]), []), "খালি");
console.log("সব JS test pass!");
```
> **JS টীকা:** `new Array(n).fill(0)` দিয়ে শুরুতেই সব `0` ভরে নাও — তাহলে "যে দিন গরম দিন পায় না" তার জন্য আলাদা কিছু লিখতে হয় না। মনে রেখো stack-এ **index** রাখছি, temperature নয়; দূরত্ব `i - j` মাপতে index লাগে। comparison-এ `temperatures[stack[...]] < temperatures[i]` — strictly বড় চাই বলে `<`, `<=` নয়।
### TypeScript ও test cases {#26-typescript-solution-with-test-cases}
```typescript
function dailyTemperatures(temperatures: number[]): number[] {
const n = temperatures.length;
const answer: number[] = new Array(n).fill(0);
const stack: number[] = []; // index-দের stack
for (let i = 0; i < n; i++) {
while (stack.length && temperatures[stack[stack.length - 1]] < temperatures[i]) {
const j = stack.pop()!;
answer[j] = i - j;
}
stack.push(i);
}
return answer;
}
function expect