014 — Daily Temperatures¶

অধ্যায় · সমস্ত অনুশীলন ও উৎস · ধাপে ধাপে শেখা

Problem link ও উৎস

Original source: Classic capstone interview problem (monotonic stack / next greater)
Platform: LeetCode — https://leetcode.com/problems/daily-temperatures/
Topic: arrays + stack
Difficulty: Medium
Pattern: Monotonic (decreasing) stack — next greater element
Basic idea inherited from: এটা একটা cross-topic capstone — এখানে মেশে 02 arrays (array-র উপর বাঁ-থেকে-ডান একবার scan আর index নিয়ে কাজ) আর stack structure (04 stack and queue) (এমন একটা stack রাখা যেটা construction-এর গুণেই sorted থাকে)। দুই tool জোড়া লাগলেই এই problem।

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

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

তোমাকে প্রতিদিনের তাপমাত্রার একটা array দেওয়া। প্রতিটা দিনের জন্য বলতে হবে: আজকের চেয়ে গরম একটা দিন পেতে আর কত দিন অপেক্ষা করতে হবে। যদি ভবিষ্যতে আর কোনো দিন আজকের চেয়ে গরম না হয়, সেই দিনের উত্তর 0। ফলাফল হবে একই দৈর্ঘ্যের একটা array, প্রতি index-এ "কত দিন পরে গরম"।

উদাহরণ

temps  : [73, 74, 75, 71, 69, 72, 76, 73]
answer : [ 1,  1,  4,  2,  1,  1,  0,  0]
যেমন: দিন 0 (73)-এর পরদিন 74 -> 1 দিন; দিন 2 (75)-এর গরম দিন index 6 (76) -> 6-2 = 4

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]   (টানা বাড়ছে)

Edge case 1 (টানা কমছে): [50,40,30]   -> [0,0,0]  (কেউ গরম দিন পায় না)
Edge case 2 (সব সমান): [40,40,40]     -> [0,0,0]  (strictly গরম লাগে)
Edge case 3 (একটা দিন): [55]          -> [0]

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

ভাবো একদল মানুষ লাইনে দাঁড়িয়ে, প্রত্যেকে একটা করে কাগজে নিজের তাপমাত্রা লিখে ধরে আছে, আর জিজ্ঞেস করছে "আমার চেয়ে গরম কেউ কখন আসবে?" তুমি একটা স্ট্যাকে অপেক্ষমাণদের রাখো — সবচেয়ে উপরে সবচেয়ে ঠান্ডা জন। নতুন একজন এলে, সে স্ট্যাকের উপরের সব ঠান্ডা মানুষের প্রশ্নের উত্তর দিয়ে দেয় ("তোমার চেয়ে গরম দিন আমি, এত দিন পরে") আর তাদের লাইন থেকে সরিয়ে দেয়। নিজে তার চেয়ে গরম কাউকে না পেলে স্ট্যাকে অপেক্ষায় বসে।

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

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

এই problem দুটো আগের chapter-এর tool জোড়া দেয়:

02 arrays থেকে: array-র উপর single pass scan, যেখানে প্রতিটা element-এর index নিয়ে কাজ করি (দিনের ব্যবধান = index-এর বিয়োগফল)।
stack structure (04 stack and queue) থেকে: একটা stack রাখা — যেখানে "এখনো গরম দিন পায়নি" এমন দিনগুলোর index জমা থাকে, আর নতুন গরম দিন এলে তারা একে একে বেরিয়ে আসে।

একা array-scan দেয় index-ভিত্তিক হাঁটা; একা stack দেয় "অপেক্ষমাণদের" মনে রাখা ও দ্রুত মীমাংসা। দুটো মিললে O(n)।

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

লুকানো logic একটা monotonic invariant: stack-এ আমরা শুধু সেই দিনগুলোর index রাখি যাদের তাপমাত্রা নিচে থেকে উপরে strictly কমছে (decreasing)। কারণ কোনো দিন j যদি stack-এর top দিন i-এর চেয়ে গরম হয়, তবে j-ই i-এর "next warmer" — তখন i-কে pop করে তার উত্তর j - i বসিয়ে দিই। যতক্ষণ top দিন এখনকার দিনের চেয়ে ঠান্ডা/সমান, ততক্ষণ pop চলে। এই "প্রতিটা index একবার push, একবার pop" সত্যটাই O(n) এনে দেয়।

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

একটা stack (Python list, 04 stack and queue) — তবে এতে তাপমাত্রা নয়, index রাখি (পরে ব্যবধান বের করতে index লাগে)।
একটা answer array (res), শুরুতে সব 0 — কোনো দিন গরম দিন না পেলে এমনিই 0 থাকে।

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

একটা দিনের "next warmer day" ঠিক করতে আমাদের দরকার — এখনো-উত্তর-পায়নি এমন আগের দিনগুলোর মধ্যে যারা এখনকার দিনের চেয়ে ঠান্ডা, তাদের সবাইকে দ্রুত খুঁজে মীমাংসা করা। একটা decreasing stack ঠিক এই কাজটা করে: top-এ সবসময় সবচেয়ে সাম্প্রতিক, সবচেয়ে ঠান্ডা অমীমাংসিত দিন থাকে, আর pop O(1)। প্রতিটা index মাত্র একবার ঢোকে-বেরোয়, তাই array-scan (02)-এর single pass-এর সাথে stack (04)-এর LIFO মীমাংসা মিলে পুরোটা O(n)-এ চলে। এই কারণেই brute force-এর nested তুলনা আর লাগে না।

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

প্রথম সরল উপায়¶

প্রথম সরল চিন্তা: প্রতিটা দিন i-এর জন্য তার পরের দিনগুলো j = i+1, i+2, ... দেখি যতক্ষণ না প্রথম গরম দিন পাই; পেলে j - i বসাই, না পেলে 0।

উদাহরণ

for i in range(n):
    for j in range(i+1, n):
        if temps[j] > temps[i]:
            res[i] = j - i
            break

কোথায় বেশি কাজ হচ্ছে¶

প্রতিটা দিনের জন্য ভিতরে আরেকটা loop — সবচেয়ে খারাপ ক্ষেত্রে (যেমন টানা কমতে থাকা তাপমাত্রা) প্রতিটা i-এর জন্য প্রায় পুরো বাকি array দেখতে হয়, মোট O(n^2)। কারণ একই "future days" বারবার scan হয়। stack (04) সেই পুনরাবৃত্তি দূর করে: প্রতিটা index একবারই push, একবারই pop হয়, তাই array-scan (02)-এর single pass-এ পুরোটা O(n)-এ নামে।

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

মূল observation: একটা গরম দিন এলে, সে এক ধাক্কায় আগের যত ঠান্ডা-অমীমাংসিত দিন আছে সবার উত্তর দিয়ে দেয়। তাই অমীমাংসিত দিনগুলোকে যদি তাপমাত্রার decreasing ক্রমে একটা stack-এ রাখি, নতুন গরম দিন top থেকে এক এক করে pop করে সবার উত্তর বসিয়ে দেয়। কোনো দিন একবার উত্তর পেলে আর তাকে দেখার দরকার নেই — এই এক চিন্তাই O(n)।

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

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

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

মোচড়: "প্রতিটা দিনের জন্য সামনে খুঁজব" ভাবার বদলে উল্টে ভাবো — "এই গরম দিনটা আগের কোন কোন অপেক্ষমাণ দিনের উত্তর হয়ে গেল?" সামনে-খোঁজার nested loop একটা stack-এ পেছনের অমীমাংসিতদের জমিয়ে এক-পাসে গলে যায়।

ছবিতে বোঝা¶

temps = [73, 74, 75, 71, 76] — stack-এ index রাখি, decreasing temp invariant:

উদাহরণ

i=0 (73)  stack খালি -> push 0          stack(idx)=[0]      temps@stack=[73]
i=1 (74)  74 > 73 -> pop 0, res[0]=1-0=1; push 1   stack=[1]      [74]
i=2 (75)  75 > 74 -> pop 1, res[1]=2-1=1; push 2   stack=[2]      [75]
i=3 (71)  71 > 75? না -> push 3          stack=[2,3]   [75,71]
i=4 (76)  76 > 71 -> pop 3, res[3]=4-3=1;
          76 > 75 -> pop 2, res[2]=4-2=2; push 4    stack=[4]     [76]

res = [1, 1, 2, 1, 0]   (stack-এ পড়ে থাকা index 4-এর উত্তর 0)

ছোট input-এ ধাপে ধাপে¶

temps = [73, 74, 71, 72]:

i=0 (73): stack খালি → push 0; stack = [0]; res = [0,0,0,0]
i=1 (74): 74 > 73 → pop 0, res[0] = 1-0 = 1; push 1; stack = [1]; res = [1,0,0,0]
i=2 (71): 71 > 74? না → push 2; stack = [1,2]
i=3 (72): 72 > 71 → pop 2, res[2] = 3-2 = 1; 72 > 74? না → push 3; stack = [1,3]
শেষ → stack-এ 1, 3 পড়ে আছে (উত্তর 0); res = [1,0,1,0]

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

Python¶

Python

def daily_temperatures(temps):
    n = len(temps)
    res = [0] * n                       # গরম দিন না পেলে 0-ই থাকবে
    stack = []                          # decreasing temp-এর index রাখি (04 stack and queue)
    for i, t in enumerate(temps):       # বাঁ-থেকে-ডান single pass (02 arrays)
        while stack and t > temps[stack[-1]]:
            prev = stack.pop()          # এই অপেক্ষমাণ দিন আজ গরম দিন পেল
            res[prev] = i - prev        # কত দিন পরে
        stack.append(i)
    return res

# ---- 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([50,40,30]) == [0,0,0]           # টানা কমছে
assert daily_temperatures([40,40,40]) == [0,0,0]           # সব সমান (strictly লাগে)
assert daily_temperatures([55]) == [0]                     # একটা দিন
assert daily_temperatures([89,62,70,58,47,47,46,76,100,70]) == [8,1,5,4,3,2,1,1,0,0]
print("সব test pass!")

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

res = [0] * n — উত্তর array, default 0; যেসব দিন গরম দিন পায় না, তাদের এমনিই 0 থাকে।
stack = [] — index-এর stack; এতে এমন দিন থাকে যাদের তাপমাত্রা নিচ থেকে উপরে কমছে।
for i, t in enumerate(temps) — index আর তাপমাত্রা নিয়ে একবার scan (02 arrays)।
while stack and t > temps[stack[-1]] — top দিনের চেয়ে আজ গরম হলে, top-এর "next warmer" পাওয়া গেছে।
prev = stack.pop(); res[prev] = i - prev — top বের করে তার উত্তর (দিনের ব্যবধান) বসাই।
stack.append(i) — এখনকার দিনকে অপেক্ষমাণ হিসেবে stack-এ রাখি।
return res — সব দিনের "কত দিন পরে গরম"।

Output মিলিয়ে দেখা¶

[73,74,75,71,69,72,76,73]-এ scan-এর সময় প্রতিটা বাড়তি তাপমাত্রা আগের ঠান্ডা দিনগুলো pop করে উত্তর বসায়; যেমন দিন 6 (76) index 2,3,4,5-কে মীমাংসা করে। শেষে index 6,7 stack-এ পড়ে থাকে, উত্তর 0 → [1,1,4,2,1,1,0,0] — assert pass। টানা-বাড়া, টানা-কমা, সব-সমান, একটা দিন, বড় mixed case — সব ঠিক। শেষে print: সব test pass!।

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

সময়¶

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

অতিরিক্ত জায়গা¶

O(n) — সবচেয়ে খারাপ ক্ষেত্রে (টানা কমা তাপমাত্রা) stack-এ একসাথে সব index জমে; res array-ও O(n)।

যে ভুলগুলো এড়াতে হবে¶

stack-এ তাপমাত্রা রাখা, index নয় — তখন দিনের ব্যবধান (i - prev) বের করা যায় না; index-ই রাখতে হবে।
> বনাম >= গুলিয়ে ফেলা — "strictly গরম" চাইলে >; সমান তাপমাত্রায় pop করলে ভুল উত্তর (সব-সমান case দেখো)।
while না করে if ব্যবহার — একটা গরম দিন একাধিক অপেক্ষমাণ দিনের উত্তর হতে পারে, তাই loop লাগে।
শেষে stack-এ পড়ে থাকা index-গুলোর উত্তর আলাদা করে 0 বসাতে চাওয়া — res আগেই 0-init করা থাকলে দরকার নেই।

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

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

ভিত্তি: array-র single-pass index scan (02 arrays, ../../02-arrays-and-strings/) + stack-এর LIFO push/pop (04 stack and queue, Stack ও Queue)। এই দুটো cold জানা থাকলে monotonic-stack চিন্তা নিজে থেকেই আসে।

পরের অনুশীলন¶

Next Greater Element II (circular array, দু'বার ঘোরা) — https://leetcode.com/problems/next-greater-element-ii/
Largest Rectangle in Histogram (একই monotonic stack, area হিসাব) — https://leetcode.com/problems/largest-rectangle-in-histogram/
Trapping Rain Water (stack বা two-pointer, দেয়ালের মাঝে জল) — https://leetcode.com/problems/trapping-rain-water/
Online Stock Span (stack-এ span জমানো) — https://leetcode.com/problems/online-stock-span/

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

Monotonic (decreasing) stack / next greater element: অমীমাংসিত index-গুলোকে decreasing ক্রমে stack-এ রেখে, নতুন বড় element এলে top থেকে pop করে তাদের উত্তর বসানো — "next greater/smaller", "কত দূর দেখা যায়"-জাতীয় problem-এর O(n) সমাধান।

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

ভবিষ্যতের আমাকে: "next greater/smaller", "কত দিন/কত দূর পর্যন্ত", histogram, span — শুনলেই monotonic stack মনে করবে। চাল — stack-এ index রাখো, এখনকার element top-এর চেয়ে বড় হলে while-loop-এ pop করে res[prev] = i - prev, তারপর push। > বনাম >= (strict কি না) আর index-বনাম-value — এই দুটোতেই বেশি ভুল হয়।

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