Skip to content

014 — Daily Temperatures

Source

  • 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/stacks) (এমন একটা stack রাখা যেটা construction-এর গুণেই sorted থাকে)। দুই tool জোড়া লাগলেই এই problem।

1. Problem in simple words

তোমাকে প্রতিদিনের তাপমাত্রার একটা 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

2. Which basic idea does this inherit from?

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

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

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

3. What is the hidden math or logic?

লুকানো 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) এনে দেয়।

4. Which data structure is needed?

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

5. Why this data structure fits

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

6. Real-life analogy

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

7. Visual explanation

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)

8. Example input and 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]

9. Brute force thinking

প্রথম সরল চিন্তা: প্রতিটা দিন 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

10. Why brute force is slow

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

11. Key observation

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

12. Optimized intuition

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

13. Thinking tweak

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

14. Step-by-step dry run

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

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

15. Python solution

def daily_temperatures(temps):
    n = len(temps)
    res = [0] * n                       # গরম দিন না পেলে 0-ই থাকবে
    stack = []                          # decreasing temp-এর index রাখি (04/stacks)
    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!")

16. Line-by-line code explanation

  • 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 — সব দিনের "কত দিন পরে গরম"।

17. Output walkthrough

[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!।

18. Time complexity

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

19. Space complexity

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

20. Common mistakes

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

21. Which basic problem this inherits from

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

22. Similar harder problems

23. Pattern learned

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

24. Final summary

ভবিষ্যতের আমাকে: "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।