009 — Daily Temperatures

Problem link ও উৎস

• Original source: Classic monotonic-stack exercise
• Platform: LeetCode — https://leetcode.com/problems/daily-temperatures/
• Topic: stack (monotonic)
• Difficulty: Medium
• Pattern: monotonic stack — next greater, distance flavor
• Basic idea inherited from: Problem 7 (next greater element) — তবে এবার value-র বদলে distance (কত দিন পরে গরম পড়বে) চাই

প্রশ্ন ও উদাহরণ

সহজ করে প্রশ্ন

তোমাকে প্রতিদিনের temperature-এর একটা list দেওয়া আছে। প্রতিটা দিনের জন্য বলতে হবে — আজকের চেয়ে কড়া গরম একটা দিন পেতে আর কত দিন অপেক্ষা করতে হবে। ভবিষ্যতে এমন কোনো গরম দিন না থাকলে সেই দিনের উত্তর 0।

মানে আউটপুটটা ঠিক ইনপুটের সমান লম্বা একটা list, যেখানে প্রতিটা ঘর "কয় দিন পরে" সেই সংখ্যাটা ধরে রাখে।

উদাহরণ

temperatures : [73, 74, 75, 71, 69, 72, 76, 73]
answer       : [ 1,  1,  4,  2,  1,  1,  0,  0]

Input ও output

উদাহরণ

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) : []         -> []

চেনা উদাহরণে বোঝা

ভাবো একটা সারিতে কয়েকজন মানুষ লাইন ধরে দাঁড়িয়ে আছে, প্রত্যেকের হাতে একটা ছোট পতাকা যাতে তাদের temperature লেখা। যতক্ষণ পরের লোকটা ঠান্ডা, ততক্ষণ আগের লোকেরা "আমার গরম দিন কই" বলে অপেক্ষায় দাঁড়িয়ে থাকে (stack-এ জমে)। হঠাৎ একজন কড়া-গরম লোক এসে দাঁড়ালে, পেছনে অপেক্ষায় থাকা সব ঠান্ডা লোক একসাথে হাত নামিয়ে বলে "পেয়েছি!" — আর তাদের কত দিন অপেক্ষা করতে হলো, সেটা গোনা হয়ে যায়।

ভিত্তির ধারণা

আগের কোন ধারণাটি লাগবে

এটা সরাসরি Problem 7 — Next Greater Element-এর বড় ভাই। সেখানে তুমি প্রতিটা element-এর ডানদিকের প্রথম strictly বড় value খুঁজছিলে; এখানেও ঠিক তাই, কিন্তু value-টা নয় — চাই তার থেকে কত index দূরে সেই বড় দিনটা। তাই answer-এ value বসানোর বদলে আমরা index-এর পার্থক্য বসাই।

এক কথায়: same monotonic-stack machinery, শুধু শেষ মুহূর্তে i - j লিখি nums[i] লেখার বদলে।

ভেতরের যুক্তি

লুকানো logic হলো একটা invariant: stack-এ আমরা শুধু সেই দিনগুলোর index রাখি যারা এখনো নিজেদের "গরম দিন" খুঁজে পায়নি, আর তাদের temperature গুলো নিচ থেকে উপর পর্যন্ত strictly কমতে থাকে (monotonic decreasing)।

এই invariant-টাই correctness দেয়: নতুন একটা দিন i যখন আসে, সে stack-এর top থেকে শুরু করে নিজের চেয়ে ছোট সব দিনকে "এই তো তোমার গরম দিন" বলে resolve করে দেয় — কারণ stack ছোট-উপরে রাখা বলে, top থেকে যতগুলো i-এর চেয়ে ঠান্ডা, তারা সবাই i-কেই তাদের প্রথম গরম দিন হিসেবে পায়।

কী দিয়ে তথ্য রাখব

একটা stack যেখানে আমরা temperature নয়, index রাখি (Python-এ সাধারণ list)। index রাখলেই দূরত্ব i - j বের করা যায়। সাথে একটা answer list যেটা শুরুতে সব 0 দিয়ে ভরা থাকে — যে দিন কখনো গরম দিন পায় না, তার জন্য 0 এমনিতেই বসে থাকবে।

এটি কেন উপযুক্ত

"প্রথম গরম দিন" মানে "সবচেয়ে কাছের ভবিষ্যতের বড় value" — আর এটা monotonic stack-এর হুবহু খেলার মাঠ। প্রতিটা দিন stack-এ একবার ঢোকে আর বড়জোর একবার বের হয়, তাই push/pop দুটোই amortized O(1)। index রাখায় দূরত্ব O(1)-তে পাওয়া যায়, আর strictly-decreasing রাখার কারণে নতুন দিন এসে শুধু তাদেরই pop করে যাদের answer সে নিজেই।

ধাপে ধাপে সমাধান

প্রথম সরল উপায়

সবচেয়ে সরল চিন্তা: প্রতিটা দিন i-এর জন্য তার ডানদিকে একটা একটা করে দিন j ঘুরে দেখি, প্রথম যেখানে temp[j] > temp[i] সেখানে থেমে j - i লিখি; না পেলে 0।

উদাহরণ

day i -> j = i+1, i+2, ... খুঁজতে থাকো প্রথম strictly বড় temperature
পেলে answer[i] = j - i; নাহলে answer[i] = 0

কোথায় বেশি কাজ হচ্ছে

প্রতিটা দিনের জন্য সবচেয়ে খারাপ ক্ষেত্রে list-এর শেষ পর্যন্ত হাঁটতে হয়। যেমন [80, 79, 78, ..., 1, 100]-এর মতো লম্বা নামতে-থাকা list-এ প্রতিটা দিন প্রায় পুরো বাকি অংশ scan করে → O(n^2)। একই দিন বারবার অন্যদের scan-এ পড়ে যায়, যা পুরো অপচয়। আমরা চাই প্রতিটা দিনকে বড়জোর একবার করে ছোঁয়া — O(n)।

যে বিষয়টি খেয়াল করতে হবে

মূল observation: একটা গরম দিন i যখন আসে, সে নিজের চেয়ে ঠান্ডা সব এখনো-অপেক্ষমাণ দিনের answer একসাথে দিয়ে দিতে পারে। আর "এখনো অপেক্ষমাণ আর ঠান্ডা" দিনগুলো ঠিক stack-এর top-এ পরপর সাজানো থাকে (strictly decreasing)। তাই সামনে খোঁজার বদলে, নতুন দিনকে দিয়ে পেছনের দিনদের answer deliver করাও।

আরও কম কাজে সমাধান

list-এ একবার বাঁ থেকে ডানে হাঁটো, index-এর একটা stack রেখে। নতুন দিন i এলে: যতক্ষণ stack খালি নয় আর top-এর দিনের temperature temp[i]-এর চেয়ে ছোট, ততক্ষণ pop করো আর pop-করা দিন j-এর জন্য answer[j] = i - j বসাও। এরপর i-কে stack-এ push করো (এখনো তার নিজের গরম দিন বাকি)। শেষে stack-এ যারা পড়ে থাকে তাদের answer 0-ই থেকে যায়।

ভাবনার পরিবর্তন

মোচড়: প্রশ্নটা উল্টে দাও। "আমার গরম দিন কোথায়" — এভাবে প্রত্যেকটা দিনকে সামনে খুঁজতে পাঠানোর বদলে, প্রতিটা নতুন দিনকে জিজ্ঞেস করো "আমি এসে কাদের অপেক্ষা শেষ করলাম?" answer push নয়, deliver করা হয় — এই উল্টো দৃষ্টিতেই O(n^2) থেকে O(n)-এ নামা।

ছবিতে বোঝা

[73, 74, 75, 71, 69, 72, 76, 73]-এর জন্য stack-এ (index রাখা, top ডানে) কী ঘটে দেখি:

উদাহরণ

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-এ ধাপে ধাপে

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]

কোড ও ব্যাখ্যা

Python

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!")

কোডের প্রতিটি অংশ

• 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 মিলিয়ে দেখা

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

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

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<T>(a: T, e: T, m = ""): void { if (a !== e) throw new Error(`FAIL ${m}`); }
const S = JSON.stringify;
expect(S(dailyTemperatures([73, 74, 75, 71, 69, 72, 76, 73])), S([1, 1, 4, 2, 1, 1, 0, 0]), "main");
expect(S(dailyTemperatures([30, 60, 90])), S([1, 1, 0]), "small");
expect(S(dailyTemperatures([90, 80, 70])), S([0, 0, 0]), "down");
expect(S(dailyTemperatures([])), S([]), "empty");
console.log("সব TS test pass!");

TS টীকা: answer: number[] ও stack: number[] টাইপ করায় ভুলে temperature push করলে (index-এর বদলে) compile-এ ধরা না পড়লেও, function signature number[] -> number[] clearly বলে দেয় ইনপুট-আউটপুট দুটোই সংখ্যার array। pop()! দিয়ে length check-এর পরে undefined সম্ভাবনা বাদ দিই — index ব্যবহারে এটা type-safe রাখে।

খরচ ও সাধারণ ভুল

সময়

O(n) — প্রতিটা index ঠিক একবার push হয় আর বড়জোর একবার pop হয়; while nested দেখালেও মোট pop সংখ্যা n-এর বেশি হতে পারে না।

অতিরিক্ত জায়গা

O(n) — সবচেয়ে খারাপ ক্ষেত্রে (যেমন strictly নামতে-থাকা [90,80,70,...]) সব index একসাথে stack-এ জমে। answer list-ও O(n), কিন্তু সেটা output বলে আলাদা করে ধরা হয় না।

যে ভুলগুলো এড়াতে হবে

• stack-এ temperature রাখা, index নয় — তাহলে দূরত্ব i - j আর বের করা যায় না।
• < আর <= গুলিয়ে ফেলা — এখানে "strictly গরম" চাই, তাই সমান temperature-কে গরম দিন ধরা যাবে না; < লাগবে, <= নয়।
• উত্তর হিসেবে nums[i] (গরম দিনের temperature) বসিয়ে ফেলা — Problem 7-এর অভ্যাসে; এখানে distance চাই।

শেখা ও পরের অনুশীলন

ভিত্তির সঙ্গে সম্পর্ক

ভিত্তি: Problem 7 (Next Greater Element I) — same monotonic-stack discipline, "most recent unfinished"। chapter-এর ../patterns.md-এর Pattern 4 (Monotonic Stack) এখানে সরাসরি; পার্থক্য শুধু আমরা index রাখি আর i - j লিখি।

পরের অনুশীলন

• Next Greater Element II (circular) — https://leetcode.com/problems/next-greater-element-ii/ (এই tracker-এর #15)
• Online Stock Span (streaming) — https://leetcode.com/problems/online-stock-span/ (#16)
• Largest Rectangle in Histogram — https://leetcode.com/problems/largest-rectangle-in-histogram/ (#20)

কৌশলটি মনে রাখুন

Monotonic stack, distance flavor: "next greater/warmer" দেখলে index-এর একটা decreasing stack রাখো; নতুন element এসে নিজের চেয়ে ছোটদের answer (এখানে দূরত্ব) deliver করে, তারপর নিজে অপেক্ষায় বসে।

নিজেকে যাচাই করুন

ভবিষ্যতের আমাকে: "কত দিন পরে গরম" = next-greater, কিন্তু distance। index-এর decreasing stack রাখো, নতুন দিন এসে ছোটদের pop করে i - j দেয়, না-পাওয়ারা 0। "until a warmer day", "next greater", "span" — এই trigger দেখলেই monotonic stack ভাববে।

কোথায় কাজে লাগে

• Weather apps: "আর কত দিন/ঘণ্টা পরে আরও গরম পড়বে" — আবহাওয়ার forecast UI-তে এই distance-flavor next-greater সরাসরি।
• Stock span / waiting time: "এই দামের পর প্রথম বড় দাম পেতে কত দিন" — trading-এ holding period অনুমান।
• Queue/SLA monitoring: request log-এ "এর পরে প্রথম কবে latency বাড়ল, কত দূরে" মাপতে।
• Manufacturing/IoT: sensor reading-এ "পরের spike কত সময় পরে" বের করতে monotonic-stack span।
• Resource scaling: load-curve-এ "পরের peak কতদূরে" দেখে auto-scaling সিদ্ধান্ত নেওয়া।

এক কথায়, "পরের বড় ঘটনা কত দূরে" — value নয়, distance — চাইলে index-এর monotonic stack রেখে O(n)-তে পুরো answer-array পাওয়া যায়।

---

মনে রাখার নিয়ম (legal): সব নিজের ভাষায় লেখা; problem statement copy করা হয়নি; official link শুধু attribution-এর জন্য; "asked by Google/Amazon" দাবি নেই — এটা একটা common interview pattern।