013 — Rotting Oranges¶

Source¶

Original source: Classic multi-source BFS exercise
Platform: LeetCode — https://leetcode.com/problems/rotting-oranges/
Topic: queue (multi-source BFS)
Difficulty: Medium
Pattern: multi-source BFS — queue
Basic idea inherited from: Problem 12 (BFS frontier), কিন্তু একসাথে কয়েকটা start নিয়ে; পূর্ণ তত্ত্ব ../../09-graphs/-এ

1. Problem in simple words¶

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

2 1 1          minute 0: শুধু (0,0) পচা
1 1 0          ...ছড়াতে ছড়াতে...
0 1 1          minute 4: সব পচে গেছে -> উত্তর 4

2. Which basic idea does this inherit from?¶

এটা Problem 12 (Number of Islands)-এর BFS-এর সরাসরি সম্প্রসারণ, একটা মোচড় নিয়ে: এক জায়গা থেকে নয়, একসাথে অনেক জায়গা থেকে ছড়ানো শুরু — এটাই multi-source BFS। শুরুর সব পচা কমলা একসাথে queue-তে থাকে যেন তারা সবাই minute 0-তে দাঁড়িয়ে আছে, তারপর সবাই একসাথে একধাপ করে ছড়ায়। পূর্ণ graph-তত্ত্ব ../../09-graphs/-এ।

3. What is the hidden math or logic?¶

লুকানো logic হলো simultaneous wavefront: সব পচা কমলাকে যদি একই BFS-এর level 0 ধরো, তাহলে BFS-এর প্রতিটা পরবর্তী level ঠিক "এক মিনিট পরের অবস্থা"। কোনো তাজা কমলায় BFS প্রথমবার পৌঁছানো মানেই — যেহেতু FIFO কোনো level-কে আগের level-এর আগে শেষ করতে দেয় না — সেটা সবচেয়ে কাছের পচা উৎস থেকে minimum সময়ে পচল।

শেষে যদি কোনো তাজা কমলা থেকে যায় (কোনো উৎসই তাকে ছুঁতে পারেনি), উত্তর -1।

4. Which data structure is needed?¶

একটা queue (collections.deque) যাতে শুরুতেই সব পচা কমলার (row, col) ঢোকানো থাকে। সাথে একটা fresh counter (কয়টা তাজা কমলা বাকি) — শেষে এটা 0 কিনা দেখে আমরা বুঝি সব পচেছে নাকি -1 দিতে হবে। আর একটা minutes counter, level-by-level গোনার জন্য।

5. Why this data structure fits¶

"প্রতি মিনিটে এক ধাপ ছড়ায়" — এটাই BFS-এর level structure। queue-র FIFO order নিশ্চিত করে minute-d-এর সব কমলা minute-(d+1)-এর কারো আগে process হয়। len(queue)-এর snapshot নিয়ে একটা পুরো level একবারে process করলে আমরা ঠিক ঠিক মিনিট গুনতে পারি। একাধিক উৎস queue-তে একসাথে থাকায় কোনো বাড়তি কাঠামো ছাড়াই "সব একসাথে ছড়াচ্ছে" ব্যাপারটা পাওয়া যায়।

6. Real-life analogy¶

একটা পুকুরের নানা জায়গায় একসাথে কয়েকটা পাথর ছুঁড়লে ভাবো। প্রতিটা পাথর থেকে ঢেউ বাইরের দিকে ছড়ায়; ঢেউগুলো একই গতিতে এগোয় আর যেখানে মেলে সেখানে মিশে যায়। পানির কোনো বিন্দু প্রথম যে ঢেউয়ে ভেজে, সেটাই তার সবচেয়ে কাছের পাথর থেকে আসা। সব পচা কমলা = একসাথে ছোঁড়া পাথর; পচন = একসাথে ছড়ানো ঢেউ।

7. Visual explanation¶

[[2,1,1],[1,1,0],[0,1,1]]-এ wavefront (minute হিসাব করি):

start: queue=[(0,0)] (একমাত্র পচা), fresh=6, minutes=0

min1: pop (0,0) -> (1,0),(0,1) পচাও        queue=[(1,0),(0,1)]  fresh=4
min2: pop (1,0),(0,1) -> (1,1),(0,2) পচাও  queue=[(1,1),(0,2)]  fresh=2
min3: pop (1,1),(0,2) -> (2,1) পচাও        queue=[(2,1)]        fresh=1
min4: pop (2,1) -> (2,2) পচাও              queue=[(2,2)]        fresh=0
fresh==0 -> থামো -> উত্তর = 4

8. Example input and output¶

Input : [[2,1,1],[1,1,0],[0,1,1]]   -> Output: 4
Input : [[2,1,1],[0,1,1],[1,0,1]]   -> Output: -1   ((2,0)-র তাজা কমলা আলাদা)
Input : [[0,2]]                      -> Output: 0    (তাজা কমলাই নেই)

Edge case 1 (একটাও পচা নেই)  : [[1]]   -> -1   (পচানোর কেউ নেই)
Edge case 2 (শুধু খালি+পচা)  : [[2,0]] -> 0    (পচানোর তাজা নেই)
Edge case 3 (সবই তাজা, ছোঁয়া যায় না): [[1,1]] -> -1

9. Brute force thinking¶

সরল চিন্তা: প্রতি মিনিটে পুরো grid scan করো; এই মিনিটে যেসব ঘর 2, তাদের তাজা প্রতিবেশীদের চিহ্নিত করে পরের scan-এ 2 বানাও; যতক্ষণ কোনো নতুন পচন ঘটে ততক্ষণ minute বাড়াও।

each minute: পুরো grid scan -> পচা কমলার পাশের তাজাদের পচাও -> minute++
কোনো নতুন পচন না হলে থামো; তখন তাজা থাকলে -1, নাহলে minute

10. Why brute force is slow¶

প্রতি মিনিটে পুরো grid নতুন করে scan করা মানে কাজটা (মিনিট সংখ্যা) × (grid আকার) — সবচেয়ে খারাপ ক্ষেত্রে এক প্রান্ত থেকে অন্য প্রান্তে পচন ছড়াতে অনেক মিনিট, প্রতিবার গোটা grid scan। multi-source BFS প্রতিটা ঘর ঠিক একবার ছোঁয়, তাই O(rows × cols)।

11. Key observation¶

মূল observation: সব পচা কমলাকে BFS-এর একই starting level-এ রাখলে, BFS-এর গভীরতা (level সংখ্যা) হুবহু মিনিট-সংখ্যা হয়ে যায়। তাই "কতগুলো মিনিট" প্রশ্নটা পরিণত হয় "multi-source BFS-এর সর্বোচ্চ distance"-এ — একবার scan-এ পাওয়া যায়।

12. Optimized intuition¶

প্রথমে পুরো grid scan করে সব পচা কমলা queue-তে ঢোকাও আর তাজা কমলা গোনো। তারপর level-by-level BFS: প্রতি iteration-এ minutes এক বাড়াও, এবং len(queue) snapshot ধরে ওই level-এর সব কমলা popleft করে তাদের তাজা প্রতিবেশীদের পচাও (grid-এ 2 লেখো, fresh কমাও, queue-তে দাও)। loop চলে যতক্ষণ queue খালি না হয় আর তাজা বাকি থাকে। শেষে fresh == 0 হলে minutes, নাহলে -1।

13. Thinking tweak¶

মোচড়: "একটা একটা করে উৎস থেকে BFS চালাই" না ভেবে ভাবো "সব উৎসকে একই super-source-এর সন্তান ধরি, সবাই minute 0-তে দাঁড়ানো"। এক BFS-এই সব wavefront সমান্তরালে চলে, আর কোনো ঘর প্রথমবার ভিজলেই সেটা minimum সময়, কারণ কোনো ঢেউ আগের ঢেউকে টপকায় না।

14. Step-by-step dry run¶

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

scan: পচা (0,0) → queue; তাজা (0,1),(1,0),(1,1) → fresh = 3; minutes = 0
queue non-empty আর fresh>0 → minutes = 1; এই level-এ (0,0) pop → (0,1) পচাও (fresh=2), (1,0) পচাও (fresh=1); queue = [(0,1),(1,0)]
minutes = 2; level: (0,1) pop → (1,1) পচাও (fresh=0); (1,0) pop → প্রতিবেশী সব পচা/সীমার বাইরে
fresh == 0 → loop থামে → 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
    for r in range(rows):                         # সব পচা একসাথে source
        for c in range(cols):
            if grid[r][c] == 2:
                queue.append((r, c))
            elif grid[r][c] == 1:
                fresh += 1
    minutes = 0
    while queue and fresh > 0:                     # level-by-level
        minutes += 1
        for _ in range(len(queue)):               # এই মিনিটের snapshot
            r, c = queue.popleft()
            for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
                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          # বাকি তাজা থাকলে -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, 0]]) == 0                             # তাজা নেই
assert oranges_rotting([[1, 1]]) == -1                            # ছোঁয়া যায় না
print("সব test pass!")

16. Line-by-line code explanation¶

প্রথম double loop — সব পচা কমলা queue-তে (multi-source), আর তাজা কমলা গুনে fresh-এ।
while queue and fresh > 0: — frontier থাকলে আর এখনো তাজা বাকি থাকলেই চালাও; fresh==0 হলে অযথা ঘোরে না।
minutes += 1 — প্রতিটা BFS level মানে এক মিনিট।
for _ in range(len(queue)): — snapshot; এই মিনিটে যারা queue-তে ছিল শুধু তাদেরই process করো, এই মিনিটে যোগ-হওয়াদের নয়।
ভেতরের if— তাজা প্রতিবেশী পেলে তাকে 2 করো, fresh কমাও, queue-তে দাও।
return minutes if fresh == 0 else -1 — সব পচলে মিনিট; কেউ বাকি থাকলে -1। (শুরুতেই fresh==0 হলে loop চলে না, minutes থাকে 0।)

17. Output walkthrough¶

oranges_rotting([[2,1,1],[1,1,0],[0,1,1]]) → section 7-এর wavefront মতো 4 মিনিটে সব পচে, fresh শেষে 0 → 4। oranges_rotting([[2,1,1],[0,1,1],[1,0,1]]) → (2,0)-র তাজা কমলা চারপাশে খালি দিয়ে ঘেরা, কখনো পচে না, শেষে fresh>0 → -1। সব assert pass করে শেষে print: সব test pass!।

18. Time complexity¶

O(rows × cols) — শুরুর scan পুরো grid একবার, আর BFS-এ প্রতিটা ঘর বড়জোর একবার enqueue/dequeue হয়।

19. Space complexity¶

O(rows × cols) — queue সবচেয়ে খারাপ ক্ষেত্রে (শুরুতেই প্রায় সব পচা, বা একসাথে অনেক ঘর frontier-এ) এতটা বড় হতে পারে।

20. Common mistakes¶

len(queue) snapshot না নিয়ে level mix করা — তখন এক মিনিটে যোগ-হওয়া কমলাও একই মিনিটে process হয়ে মিনিট গণনা ভুল হয়।
শুরুতে তাজা কমলা না গোনা — -1 কেস (কেউ পচে না) ধরা যায় না।
fresh==0-এর প্রাথমিক কেস ভুলে যাওয়া — তাজা কমলা না থাকলে উত্তর 0, -1 নয়; loop না চললে minutes 0-ই থাকে বলে এটা এমনিতেই ঠিক হয়।

21. Which basic problem this inherits from¶

ভিত্তি: Problem 12-এর single-source BFS, এখানে multi-source-এ সম্প্রসারিত। chapter-এর ../patterns.md-এর Pattern 2 (BFS Frontier) এখানে layered/multi-source রূপে; পূর্ণ আলোচনা ../../09-graphs/-এ।

22. Similar harder problems¶

01 Matrix (নিকটতম 0 পর্যন্ত দূরত্ব, multi-source BFS) — https://leetcode.com/problems/01-matrix/
Walls and Gates — https://leetcode.com/problems/walls-and-gates/
As Far from Land as Possible — https://leetcode.com/problems/as-far-from-land-as-possible/

23. Pattern learned¶

Multi-source BFS: "সব start থেকে একসাথে ছড়ায়", "কত মিনিট/ধাপে সব ছেয়ে যায়" দেখলে শুরুর সব উৎস একসাথে queue-তে দাও, level-by-level (snapshot) BFS চালাও — level সংখ্যাই সময়।

24. Final summary¶

ভবিষ্যতের আমাকে: সব পচা একসাথে queue-তে (level 0), তাজা গোনো, level-by-level snapshot BFS — level সংখ্যা = মিনিট। শেষে fresh>0 হলে -1। "spreads each minute", "multi-source", "minimum time to fill" দেখলে এই pattern; গভীরতর তত্ত্ব ../../09-graphs/।

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