Skip to content

009 — Rotting Oranges

Source

  • Original source: Classic capstone interview problem (multi-source BFS)
  • Platform: LeetCode — https://leetcode.com/problems/rotting-oranges/
  • Topic: graphs (BFS) + grid indexing
  • Difficulty: Medium
  • Pattern: Multi-source BFS, counting levels (minutes)
  • Basic idea inherited from: এটা একটা cross-topic capstone — এখানে মেশে 09 graphs (BFS দিয়ে level-by-level ছড়ানো, যেখানে একসাথে অনেক উৎস থেকে শুরু — multi-source) আর 02 grid indexing (grid-এর cell গুলোকে (r, c) দিয়ে ধরা, চার প্রতিবেশীতে যাওয়া)। দুই tool জোড়া লাগলেই এই problem।

1. Problem in simple words

তোমাকে একটা grid দেওয়া, যেখানে প্রতিটা ঘর — 0 (ফাঁকা), 1 (তাজা কমলা), বা 2 (পচা কমলা)। প্রতি মিনিটে, প্রতিটা পচা কমলা তার পাশের (উপর-নিচ-বাঁ-ডান) তাজা কমলাগুলোকেও পচিয়ে দেয়। প্রশ্ন: সব তাজা কমলা পচতে সর্বনিম্ন কত মিনিট লাগবে? যদি কখনো কোনো তাজা কমলা পচানো অসম্ভব হয় (চারপাশে কেউ নেই), তাহলে -1 ফেরত দাও।

শুরু (minute 0):      minute 1:        minute 2:
2 1 1                 2 2 1            2 2 2
1 1 0        ->       2 1 0      ->    2 2 0      -> সব পচা; উত্তর = 2 (এই উদাহরণে 4)
0 1 1                 0 1 1            0 2 1   ...

2. Which basic idea does this inherit from?

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

  • 09 graphs থেকে: BFS — যেটা level-by-level ছড়ায়, তাই "কত ধাপ/মিনিট লাগল" সরাসরি গোনা যায়। এখানে মোচড়: একটা উৎস না, অনেক পচা কমলা একসাথে উৎস (multi-source BFS)।
  • 02 grid indexing থেকে: cell গুলোকে (r, c) দিয়ে ধরা আর চার দিকে ((r±1,c), (r,c±1)) যাওয়ার সূত্র।

একা BFS দেয় shortest-time framing; একা grid-indexing দেয় প্রতিবেশীতে যাওয়ার কৌশল। দুটো মিললে minutes গোনা সহজ।

3. What is the hidden math or logic?

লুকানো logic: BFS-এর প্রতিটা level হলো এক মিনিট। শুরুতে সব পচা কমলা একসাথে queue-তে (level 0)। প্রতিটা level পুরো process করা মানে এক মিনিট কেটে যাওয়া, আর সেই মিনিটে যেসব তাজা কমলা পচল তারা পরের level। যেহেতু BFS সবচেয়ে ছোট দূরত্ব দেয়, প্রতিটা তাজা কমলা ঠিক যত মিনিটে পচা সম্ভব ততটাতেই পচে — তাই শেষ level-এর সংখ্যা = সর্বনিম্ন মিনিট।

4. Which data structure is needed?

একটা queue (Python-এ collections.deque) — BFS-এর হৃদয়, FIFO ক্রমে cell বের করে। সাথে একটা fresh counter (কত তাজা কমলা বাকি) আর minutes counter। grid নিজেই visited চিহ্ন রাখে (পচালে 2 করে দিই)।

5. Why this data structure fits

আমরা চাই সব উৎস থেকে একই গতিতে, level ধরে ধরে ছড়াতে — যাতে minute-এর হিসাব নিখুঁত থাকে। queue (FIFO) ঠিক এটাই দেয়: যা আগে ঢুকেছে আগে বের হয়, তাই কাছের cell আগে process হয়। DFS/stack এখানে কাজ করবে না, কারণ সেটা গভীরে চলে যায়, level ভেঙে ফেলে — minute-গণনা গোলমাল হতো। এজন্যই BFS-queue (09) + grid-indexing (02) এখানে নিখুঁত।

6. Real-life analogy

ভাবো একটা মাঠে কয়েক জায়গায় একসাথে আগুন লাগল (multi-source)। প্রতি মিনিটে আগুন তার ঠিক পাশের ঘাসে ছড়ায়। তুমি জানতে চাও পুরো মাঠ পুড়তে কত মিনিট লাগবে। সব আগুন একসাথে সমান গতিতে বাড়ে — তাই তুমি "এই মিনিটের আগুনের সীমানা" পুরোটা ছড়ানোর পর ঘড়িতে এক মিনিট যোগ করো, তারপর পরের সীমানা। কোথাও ঘাস থেকে গেলে যেখানে আগুন পৌঁছায় না — সেটাই -1।

7. Visual explanation

2 1 1 / 1 1 0 / 0 1 1 — minute ধরে ধরে (* = এইমাত্র পচল):

minute 0 queue: [(0,0)]      grid: 2 1 1 / 1 1 0 / 0 1 1   fresh=6
--- minute 1 process করে ---
(0,0) থেকে: (0,1),(1,0) পচল   grid: 2 2* 1 / 2* 1 0 / 0 1 1  fresh=4
--- minute 2 ---
(0,1)->(0,2); (1,0)->(1,1)    grid: 2 2 2* / 2 2* 0 / 0 1 1  fresh=2
--- minute 3 ---
(1,1)->(2,1)                   grid: 2 2 2 / 2 2 0 / 0 2* 1  fresh=1
--- minute 4 ---
(2,1)->(2,2)                   grid: ... / 0 2 2*            fresh=0
fresh=0 -> উত্তর = 4 মিনিট

8. Example input and output

Input :
2 1 1
1 1 0
0 1 1
Output: 4

Edge case 1 (পৌঁছানো অসম্ভব):
2 1 1
0 1 1
1 0 1            -> Output: -1   # নিচ-বাঁয়ের তাজা কমলা বিচ্ছিন্ন
Edge case 2 (কোনো তাজা নেই): [[0,2]] -> Output: 0   # পচানোর কিছু নেই
Edge case 3 (শুধু ফাঁকা/পচা): [[0,0]] -> Output: 0

9. Brute force thinking

প্রথম সরল চিন্তা: simulation — বারবার পুরো grid scan করো; প্রতি pass-এ যত পচা কমলা আছে তাদের তাজা প্রতিবেশীদের পচাও, এক মিনিট যোগ করো; যতক্ষণ কোনো নতুন কমলা পচছে চালিয়ে যাও।

minute = 0
while কোনো নতুন পচা হচ্ছে:
    এই মুহূর্তের সব পচা কমলা খুঁজে তাদের প্রতিবেশী পচাও (পরের pass-এর জন্য চিহ্নিত করো)
    minute += 1
শেষে fresh বাকি থাকলে -1

10. Why brute force is slow

প্রতি মিনিটে পুরো grid আবার scan করা মানে worst case O((rows·cols)^2) — কারণ মিনিট সংখ্যা grid-আকারের সমান হতে পারে, আর প্রতি মিনিটে পুরো grid দেখা হয়। BFS-queue সেই অপচয় মুছে দেয়: প্রতিটা cell ঠিক একবার queue-তে ঢোকে-বেরোয়, তাই মোট O(rows·cols)।

11. Key observation

মূল observation: সব পচা কমলা একসাথে সমান গতিতে ছড়ায়, তাই এটা multi-source BFS — শুরুতেই সব পচা কমলা queue-তে দিয়ে দাও। তখন BFS-এর প্রতিটা সম্পূর্ণ level = এক মিনিট, আর শেষ level-এর সংখ্যাই উত্তর। এই এক চিন্তাই simulation-এর পুনরাবৃত্তি মুছে দেয়।

12. Optimized intuition

শুরুতে grid scan করে সব পচা কমলা queue-তে ঢালো, আর তাজা কমলা গুনে রাখো (fresh)। তারপর level-by-level BFS: প্রতি level-এ queue-র বর্তমান সব cell বের করে তাদের তাজা প্রতিবেশীদের পচাও (queue-তে যোগ করো, fresh কমাও)। একটা level-এ যদি অন্তত একটা নতুন পচা হয়, minutes এক বাড়াও। শেষে fresh == 0 হলে minutes, নাহলে -1।

13. Thinking tweak

মোচড়: "একটা উৎস থেকে BFS" ভাবার বদলে ভাবো "সব উৎস একসাথে queue-তে ঢুকিয়ে দিই — তখন level মানেই মিনিট।" multi-source-এর এই চালেই simulation একটা পরিষ্কার BFS-এ গলে যায়।

14. Step-by-step dry run

Input [[2,1],[0,1]]:

  1. scan: পচা (0,0) queue-তে; fresh = 2 ((0,1), (1,1)); minutes = 0
  2. level 1: (0,0) বের → প্রতিবেশী (0,1) তাজা → পচাও, queue-তে; (1,0) ফাঁকা; fresh = 1; এই level-এ পচা হয়েছে → minutes = 1
  3. level 2: (0,1) বের → প্রতিবেশী (1,1) তাজা → পচাও, queue-তে; fresh = 0; minutes = 2
  4. level 3: (1,1) বের → কোনো তাজা প্রতিবেশী নেই → নতুন পচা নেই, minutes বাড়ে না
  5. fresh == 0 → return minutes = 2

15. Python solution

from collections import deque

def oranges_rotting(grid):
    rows, cols = len(grid), len(grid[0])
    queue = deque()
    fresh = 0
    # শুরুর সব পচা কমলা = BFS-এর উৎস; তাজা গুনে রাখো
    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == 2:
                queue.append((r, c))
            elif grid[r][c] == 1:
                fresh += 1

    if fresh == 0:
        return 0                       # পচানোর কিছুই নেই

    minutes = 0
    directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]
    while queue and fresh > 0:
        minutes += 1                   # একটা নতুন মিনিট শুরু
        for _ in range(len(queue)):    # ঠিক এই level-এর cell গুলো
            r, c = queue.popleft()
            for dr, dc in directions:
                nr, nc = r + dr, c + dc
                if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] == 1:
                    grid[nr][nc] = 2   # পচাও
                    fresh -= 1
                    queue.append((nr, nc))
    return minutes if fresh == 0 else -1

# ---- tests ----
assert oranges_rotting([[2,1,1],[1,1,0],[0,1,1]]) == 4
assert oranges_rotting([[2,1,1],[0,1,1],[1,0,1]]) == -1   # বিচ্ছিন্ন তাজা
assert oranges_rotting([[0,2]]) == 0                      # কোনো তাজা নেই
assert oranges_rotting([[1]]) == -1                       # একা তাজা, উৎস নেই
assert oranges_rotting([[2,2],[1,1]]) == 1               # এক মিনিটেই সব
print("সব test pass!")

16. Line-by-line code explanation

  • প্রথম double loop — grid scan করে সব পচা cell queue-তে (multi-source উৎস), তাজা সংখ্যা fresh-এ।
  • if fresh == 0: return 0 — শুরুতেই কোনো তাজা কমলা না থাকলে 0 মিনিট।
  • directions — চার প্রতিবেশীর offset (02 grid indexing)।
  • while queue and fresh > 0 — যতক্ষণ ছড়ানোর জায়গা আর বাকি তাজা আছে।
  • minutes += 1 — এই level শুরু = এক মিনিট।
  • for _ in range(len(queue)) — এই মুহূর্তের level-এর ঠিক যতগুলো cell, ততবার — এটাই level আলাদা রাখে।
  • popleft() — FIFO, BFS-এর queue।
  • boundary + == 1 চেক — সীমার ভেতরে আর তাজা হলেই পচাও, fresh কমাও, queue-তে দাও।
  • return minutes if fresh == 0 else -1 — সব পচলে minutes, নাহলে পৌঁছানো গেল না → -1।

17. Output walkthrough

[[2,1,1],[1,1,0],[0,1,1]]-এ একটামাত্র উৎস (0,0) থেকে ছড়িয়ে level গুনতে গুনতে minute 1,2,3,4-এ সব তাজা কমলা পচে, fresh 0 হয় → return 4 — assert pass। বিচ্ছিন্ন তাজা থাকলে শেষে fresh > 0, return -1; কোনো তাজা না থাকলে 0; একা তাজা কমলায় উৎস নেই, return -1। শেষে print: সব test pass!।

18. Time complexity

O(rows · cols) — scan একবার, আর প্রতিটা cell queue-তে সর্বোচ্চ একবার ঢোকে-বেরোয়।

19. Space complexity

O(rows · cols) — worst case queue-তে অনেক cell একসাথে থাকতে পারে।

20. Common mistakes

  • শুরুর সব পচা কমলা একসাথে queue-তে না দেওয়া — multi-source না হলে minute-হিসাব ভুল হয়।
  • level আলাদা না করা (for _ in range(len(queue)) বাদ) — তখন এক মিনিটে কত cell process হলো গুলিয়ে যায়, minute ভুল।
  • শেষে অবশিষ্ট fresh চেক না করা — বিচ্ছিন্ন কমলার জন্য -1 ফেরত দিতে ভুলে যাওয়া।
  • শুরুতে fresh == 0 case বাদ — তখন অযথা minutes বেড়ে ভুল উত্তর (0-র বদলে) আসতে পারে।

21. Which basic problem this inherits from

ভিত্তি: graph-এ BFS / shortest-path-by-levels (09 graphs, ../../09-graphs/) + grid-এ (r,c) indexing ও 4-direction move (02 arrays/grid, ../../02-arrays-and-strings/)। একক-উৎস BFS-এর সরাসরি সম্প্রসারণ — শুধু শুরুতে একাধিক উৎস।

22. Similar harder problems

23. Pattern learned

Multi-source BFS by levels: সব উৎস একসাথে queue-তে দিয়ে, প্রতিটা সম্পূর্ণ level-কে এক "ধাপ/মিনিট" ধরে ছড়ানো — "একসাথে অনেক জায়গা থেকে সমান গতিতে ছড়ানো, কত ধাপ লাগল" — এই ধরনের problem-এর canonical চাল।

24. Final summary

ভবিষ্যতের আমাকে: "একসাথে অনেক জায়গা থেকে ছড়ায়, সর্বনিম্ন সময়/ধাপ" শুনলেই multi-source BFS মনে করবে। মূল চাল — শুরুতেই সব উৎস queue-তে ঢালো, আর for _ in range(len(queue)) দিয়ে level আলাদা রেখে ধাপ গোনো। শেষে অবশিষ্ট target চেক করে "পৌঁছানো গেল না → -1" বলতে ভুলো না।

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