008 — Rotting Oranges

Source

• Original source: Classic multi-source BFS exercise
• Platform: LeetCode — https://leetcode.com/problems/rotting-oranges/
• Topic: graphs
• Difficulty: Medium
• Pattern: multi-source BFS on a grid (answer = number of levels)
• Basic idea inherited from: queue দিয়ে BFS (../../04-stack-and-queue/, ../bfs.md); level-by-level expansion

1. Problem in simple words

তোমাকে একটা m x n grid দেওয়া আছে, যেখানে প্রতিটা cell-এর মান 0 (খালি), 1 (তাজা কমলা), বা 2 (পচা কমলা)। প্রতি মিনিটে যেকোনো পচা কমলার চার দিকের (উপর-নিচ-বাম-ডান) তাজা প্রতিবেশী কমলাগুলো পচে যায়। বলো: সব কমলা পচতে কত মিনিট লাগবে। যদি কোনো তাজা কমলা কখনোই পচতে না পারে (চারদিকে আটকা / পচা থেকে দূরে), তাহলে -1।

grid (0=খালি, 1=তাজা, 2=পচা):
  2 1 1
  1 1 0
  0 1 1      <- সব পচতে লাগে 4 মিনিট

2. Which basic idea does this inherit from?

মূল ভিত হলো queue দিয়ে BFS (../../04-stack-and-queue/, ../bfs.md), বিশেষ করে তার multi-source রূপ। পচন একটা ঢেউয়ের মতো একসাথে ছড়ায় — সব পচা কমলা থেকে একসাথে। BFS-এর সৌন্দর্য: queue-টা শুধু একটা start দিয়ে নয়, সব পচা কমলা দিয়ে শুরু করো (সবাই minute 0-এ); তারপর সাধারণ BFS চললেই প্রতিটা তাজা কমলা পায় তার nearest পচা কমলা থেকে সময়। উত্তর = মোট কত level লাগল।

3. What is the hidden math or logic?

লুকানো logic: সমান-cost ছড়ানোয় BFS-এর level সংখ্যা = সময়। প্রতিটা মিনিট হলো BFS-এর এক layer; layer 0 = প্রথম থেকে পচা সব কমলা, layer 1 = তাদের প্রতিবেশী, layer 2 = তাদেরও প্রতিবেশী — এভাবে। সব sources একসাথে queue-তে থাকায় ঢেউগুলো মেলে, আর প্রতিটা তাজা কমলা পচে যায় তার সবচেয়ে কাছের পচা কমলার সময়ে (BFS-এর first-arrival = shortest)। শেষ যে layer-এ নতুন কমলা পচল, সেটাই মোট মিনিট। শেষে কোনো তাজা কমলা বাকি থাকলে — অপৌঁছনীয়, তাই -1।

4. Which data structure is needed?

• Grid নিজেই — implicit graph; neighbor চার দিকের cell।
• collections.deque — BFS frontier; multi-source বলে শুরুতেই সব পচা কমলা ঢোকে।
• fresh counter — কতগুলো তাজা কমলা এখনো পচেনি, শেষে -1 নাকি minute সিদ্ধান্তে।
• distance/minute চিহ্ন — হয় cell-এর সাথে সময় store করে (2 করে দিয়ে), নয়তো level-by-level গুনে।

5. Why this data structure fits

Grid-কে graph ধরা fit করে কারণ neighbor সম্পর্ক চার দিকেই fixed। deque fit করে কারণ BFS-এর গোটা চরিত্রই FIFO — যা আগে পচল, তার প্রতিবেশী আগে পচায়; list.pop(0) হলে quadratic হয়ে যেত। multi-source seeding fit করে কারণ পচন আক্ষরিক অর্থেই একাধিক জায়গা থেকে একসাথে ছড়ায় — এক পাথরের বদলে এক মুঠো পাথর পুকুরে ফেলার মতো, একই ঢেউ একই code।

6. Real-life analogy

ঝুড়িভর্তি কমলার মধ্যে কয়েকটা আগেই পচা ভাবো। পচন ছোঁয়াচে — প্রতি রাতে প্রতিটা পচা কমলা তার গা-ঘেঁষা তাজা কমলাগুলোকে পচিয়ে দেয়। সব পচা কমলা একসাথে এই কাজ করে, তাই পচন একসাথে অনেক জায়গা থেকে ছড়ায়। কত রাতে পুরো ঝুড়ি পচবে? — এটাই উত্তর। আর কোনো তাজা কমলা যদি চারপাশে খালি জায়গা/দেয়ালে আটকে পচা থেকে বিচ্ছিন্ন থাকে, সে কখনো পচবে না — তখন উত্তর -1।

7. Visual explanation

grid = [[2,1,1],[1,1,0],[0,1,1]] দিয়ে minute-by-minute:

minute 0:        minute 1:        minute 2:        minute 3:        minute 4:
  2 1 1            2 2 1            2 2 2            2 2 2            2 2 2
  1 1 0            2 1 0            2 2 0            2 2 0            2 2 0
  0 1 1            0 1 1            0 1 1            0 2 1            0 2 2

source (minute 0): শুধু (0,0)।  ঢেউ ছড়ায় চার দিকে।
সব কমলা পচল minute 4-এ  ->  উত্তর 4

8. Example input and output

Input : grid = [[2,1,1],[1,1,0],[0,1,1]]
Output: 4

Input : grid = [[2,1,1],[0,1,1],[1,0,1]]
Output: -1        (নিচ-বাঁয়ের (2,0) কমলা কখনো পচা ছোঁবে না)

Edge case (কোনো তাজা কমলাই নেই): grid = [[0,2]] -> 0 (শুরুতেই সব "পচা/খালি")

9. Brute force thinking

প্রথম সরল চিন্তা: minute-কে simulate করা grid বারবার scan করে — প্রতি minute-এ পুরো grid ঘুরে যেসব তাজা কমলার কোনো পচা প্রতিবেশী আছে তাদের চিহ্নিত করো, তারপর সবাইকে একসাথে পচাও; এভাবে যতক্ষণ না কোনো নতুন কমলা পচে।

1) minute = 0
2) পুরো grid scan করে পচার-যোগ্য তাজা কমলা খুঁজে একসাথে পচাও
3) এই minute-এ কিছু পচলে minute += 1, ধাপ 2-এ ফেরো; না পচলে থামো
4) তাজা কমলা বাকি থাকলে -1, নাহলে minute

10. Why brute force is slow

প্রতি minute-এ পুরো grid rescan করা মানে worst case প্রতিটা minute-এ O(m·n) কাজ, আর minute সংখ্যা O(m·n) হতে পারে — মোট O((m·n)^2)-এর দিকে। অথচ multi-source BFS প্রতিটা cell ঠিক একবার queue-তে ঢোকায় আর একবার বের করে, পচনের ঢেউ স্বাভাবিকভাবেই level ধরে এগোয় — মোট O(m·n)। rescan-এর অপচয়টাই মূল পার্থক্য।

11. Key observation

মূল observation: সব পচা কমলাকে একই সাথে BFS-এর source ধরো (minute 0), তারপর level সংখ্যাই মোট সময়। আলাদা করে প্রতিটা পচা থেকে BFS চালানোর দরকার নেই — একটাই BFS, একগুচ্ছ start। আর শেষে তাজা কমলা গোনা থাকলে বুঝবে কেউ অপৌঁছনীয় ছিল।

12. Optimized intuition

প্রথমে grid scan করো: সব পচা কমলা queue-তে ঢোকাও (minute 0), আর তাজা কমলার সংখ্যা fresh গোনো। তারপর level-by-level BFS: প্রতি round-এ বর্তমান queue-র সব কমলা pop করে তাদের তাজা প্রতিবেশী পচাও (queue-তে যোগ করো, fresh -= 1)। round শেষ হলে minutes += 1 (যদি কিছু পচে থাকে)। BFS শেষে fresh == 0 হলে minutes, নাহলে -1। O(m·n)।

13. Thinking tweak

মোচড়: "প্রতিটা পচা কমলা থেকে আলাদা করে দূরত্ব মাপব" বা "প্রতি minute-এ পুরো grid ঘুরব" না ভেবে ভাবো "সব পচা কমলাকে একসাথে queue-তে বসিয়ে দিই — এক BFS, ঢেউগুলো নিজেই মিলে যাবে, আর level-ই সময়।" বহু BFS / rescan থেকে নেমে এসো একটাই multi-source BFS-এ।

14. Step-by-step dry run

grid = [[2,1,1],[0,1,1],[1,0,1]]:

1. scan: পচা (0,0) → queue। তাজা: (0,1),(0,2),(1,1),(1,2),(2,0),(2,2) → fresh = 6।
2. round 1: pop (0,0) → প্রতিবেশী (0,1) তাজা পচাও (fresh=5), (1,0)=0 বাদ। minutes=1।
3. round 2: pop (0,1) → (0,2) পচাও (fresh=4), (1,1) পচাও (fresh=3)। minutes=2।
4. round 3: pop (0,2),(1,1) → (1,2) পচাও (fresh=2); (2,1)=0। minutes=3।
5. round 4: pop (1,2) → (2,2) পচাও (fresh=1)। minutes=4।
6. round 5: pop (2,2) → প্রতিবেশী সব পচা/0/বাইরে। কিছু পচল না।
7. queue খালি, কিন্তু (2,0) তাজা রয়ে গেল (fresh = 1 > 0) → return -1।

15. Python solution

from collections import deque


def oranges_rotting(grid):
    R, C = len(grid), len(grid[0])
    q = deque()
    fresh = 0
    # multi-source seeding: সব পচা কমলা minute 0-তে
    for r in range(R):
        for c in range(C):
            if grid[r][c] == 2:
                q.append((r, c))
            elif grid[r][c] == 1:
                fresh += 1

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

    minutes = 0
    while q:
        # এই level-এ এখন যত পচা কমলা আছে, সবাইকে process করো
        for _ in range(len(q)):
            r, c = q.popleft()
            for dr, dc in ((-1, 0), (1, 0), (0, -1), (0, 1)):
                nr, nc = r + dr, c + dc
                if (0 <= nr < R and 0 <= nc < C and grid[nr][nc] == 1):
                    grid[nr][nc] = 2      # পচিয়ে দেওয়াই visited-marking
                    fresh -= 1
                    q.append((nr, nc))    # পরের ঢেউয়ের জন্য
        if q:                             # এই round-এ নতুন কিছু পচল
            minutes += 1

    return minutes if fresh == 0 else -1  # বাকি তাজা থাকলে অপৌঁছনীয়


# ---- tests ----
g1 = [[2, 1, 1], [1, 1, 0], [0, 1, 1]]
g2 = [[2, 1, 1], [0, 1, 1], [1, 0, 1]]
g3 = [[0, 2]]
g4 = [[2, 2], [1, 1]]

assert oranges_rotting([row[:] for row in g1]) == 4
assert oranges_rotting([row[:] for row in g2]) == -1
assert oranges_rotting([row[:] for row in g3]) == 0     # তাজা কমলা নেই
assert oranges_rotting([row[:] for row in g4]) == 1
print("সব test pass!")

16. Line-by-line code explanation

• প্রথম double loop — সব পচা কমলা queue-তে (multi-source), আর তাজা কমলা fresh-এ গোনা।
• if fresh == 0: return 0 — পচানোর মতো তাজা কমলাই নেই, সময় 0।
• for _ in range(len(q)) — round শুরুর মুহূর্তে queue-তে যত কমলা, ঠিক ততটা pop; এটাই এক level সীমাবদ্ধ করে।
• if 0 <= nr < R and 0 <= nc < C and grid[nr][nc] == 1 — bounds আগে, তারপর তাজা প্রতিবেশী।
• grid[nr][nc] = 2 — পচানোই visited-marking; আলাদা set লাগে না, একই কমলা দুবার পচে না।
• if q: minutes += 1 — round-এ নতুন কমলা যোগ হলেই minute বাড়ে; শেষ খালি round যেন বাড়তি minute না দেয়।
• return minutes if fresh == 0 else -1 — সব পচলে সময়, নাহলে অপৌঁছনীয়।

17. Output walkthrough

oranges_rotting(g1): একমাত্র source (0,0) থেকে ঢেউ চার level-এ সব কমলা পচায় → 4। g2-তে (2,0) অপৌঁছনীয় থেকে যায় → -1। g3-এ তাজা কমলা নেই → 0। g4-এ এক round-এ নিচের সারি পচে → 1। সব assert pass, শেষে print: সব test pass!।

18. Time complexity

O(m · n) — initial scan সব cell একবার; BFS-এ প্রতিটা cell বড়জোর একবার queue-তে ঢোকে ও বের হয়, প্রতিটা প্রতিবেশী constant-বার দেখা হয়।

19. Space complexity

O(m · n) — worst case queue পুরো এক level (গ্রিড-আকারের) ধরে রাখতে পারে, যেমন প্রায় সব কমলা শুরুতেই পচা থাকলে। in-place পচানোয় আলাদা visited বাঁচে।

20. Common mistakes

• single-source ভেবে শুধু একটা পচা কমলা থেকে BFS — সব পচা কমলা একসাথে seed করতে হবে।
• শেষে fresh চেক না করা — অপৌঁছনীয় তাজা কমলা থাকলেও ভুল করে একটা সময় ফেরত দেওয়া।
• শেষ খালি round-এ minutes বাড়িয়ে এক বেশি গোনা — if q: দিয়ে রক্ষা করো, বা minute-কে cell-এর সাথে store করো।
• len(q) snapshot না নিয়ে loop-এর ভেতরে q বদলাতে থাকা — তাহলে level সীমা ভেঙে যায়; round শুরুতেই len(q) ধরো।

21. Which basic problem this inherits from

ভিত্তি: queue-র FIFO (../../04-stack-and-queue/) আর BFS level-expansion (../bfs.md)। এটা প্রথম multi-source BFS problem এই tracker-এ — single start থেকে নয়, একগুচ্ছ start থেকে একই ঢেউ। মূল শিক্ষা: "একসাথে ছড়ায় / nearest source পর্যন্ত সময়" মানেই queue-টা সব source দিয়ে শুরু করা — এক extra seeding লাইন, বাকি BFS অপরিবর্তিত। পরের ধাপ: একই multi-source idea-তে প্রতিটা cell-এর nearest 0-এর দূরত্ব (#9)।

22. Similar harder problems

• 01 Matrix (প্রতিটা cell-এর nearest 0-এর দূরত্ব, multi-source) — https://leetcode.com/problems/01-matrix/ (এই tracker-এর #9)
• Walls and Gates (প্রতিটা ঘর থেকে nearest gate) — https://leetcode.com/problems/walls-and-gates/
• As Far from Land as Possible (multi-source BFS, সর্বোচ্চ দূরত্ব) — https://leetcode.com/problems/as-far-from-land-as-possible/

23. Pattern learned

Multi-source BFS: "একসাথে অনেক জায়গা থেকে ছড়ায়", "সব কিছুতে পৌঁছাতে কত round", "nearest X পর্যন্ত সময়" — সব ক্ষেত্রে queue-টা শুরু করো সব source দিয়ে, distance 0-তে। ঢেউগুলো মেলে, প্রতিটা cell পায় nearest source-এর দূরত্ব, আর level সংখ্যাই উত্তর। খরচ O(m·n)।

24. Final summary

ভবিষ্যতের আমাকে: "rotting oranges = multi-source BFS; সব পচা কমলা একসাথে queue-তে, level = মিনিট, শেষে তাজা বাকি থাকলে -1।" যখনই 'একসাথে ছড়ানো / nearest source পর্যন্ত সময়' দেখবে — single start-এর কথা ভুলে সব source seed করো; এক লাইন বদলে BFS-টাই উত্তর দেয়।

25. JavaScript solution (with test cases)

const assert = (cond, msg = "") => { if (!cond) throw new Error("FAIL " + msg); };

function orangesRotting(grid) {
  const R = grid.length, C = grid[0].length;
  let q = [];                                  // BFS frontier (এক level)
  let fresh = 0;
  // multi-source seeding: সব পচা কমলা minute 0-তে
  for (let r = 0; r < R; r++) {
    for (let c = 0; c < C; c++) {
      if (grid[r][c] === 2) q.push([r, c]);
      else if (grid[r][c] === 1) fresh++;
    }
  }
  if (fresh === 0) return 0;                    // পচানোর মতো কিছুই নেই

  const dirs = [[-1, 0], [1, 0], [0, -1], [0, 1]];
  let minutes = 0;
  while (q.length > 0) {
    const next = [];                           // এই round-এ যারা নতুন পচল
    for (const [r, c] of q) {                   // q = ঠিক এই minute-এর পচা কমলা
      for (const [dr, dc] of dirs) {
        const nr = r + dr, nc = c + dc;
        if (nr >= 0 && nr < R && nc >= 0 && nc < C && grid[nr][nc] === 1) {
          grid[nr][nc] = 2;                     // পচিয়ে দেওয়াই visited-marking
          fresh--;
          next.push([nr, nc]);                  // পরের ঢেউয়ের জন্য
        }
      }
    }
    q = next;
    if (q.length > 0) minutes++;                // এই round-এ নতুন কিছু পচল
  }
  return fresh === 0 ? minutes : -1;            // বাকি তাজা থাকলে অপৌঁছনীয়
}

const clone = (g) => g.map((row) => row.slice());

// ---- test cases ----
const g1 = [[2, 1, 1], [1, 1, 0], [0, 1, 1]];
const g2 = [[2, 1, 1], [0, 1, 1], [1, 0, 1]];
const g3 = [[0, 2]];
const g4 = [[2, 2], [1, 1]];
assert(orangesRotting(clone(g1)) === 4, "g1");
assert(orangesRotting(clone(g2)) === -1, "g2 অপৌঁছনীয়");
assert(orangesRotting(clone(g3)) === 0, "তাজা নেই");
assert(orangesRotting(clone(g4)) === 1, "এক round");
console.log("সব JS test pass!");

JS টীকা: Python-এ for _ in range(len(q)) দিয়ে level snapshot নেওয়া হয়; JS-এ এখানে আরও পরিষ্কার — পুরো বর্তমান q-এর উপর for...of চালিয়ে নতুন-পচা কমলাগুলো একটা আলাদা next array-তে জমিয়ে, q = next দিয়ে পরের minute-এ লাফ। এতে shift()-এর O(n) এড়ানো যায় আর level (minute) সীমা ঠিক থাকে। in-place 2 করে দেওয়াই visited-mark, আলাদা set লাগে না।

26. TypeScript solution (with test cases)

type Grid = number[][];

function orangesRotting(grid: Grid): number {
  const R = grid.length, C = grid[0].length;
  let q: [number, number][] = [];
  let fresh = 0;
  for (let r = 0; r < R; r++) {
    for (let c = 0; c < C; c++) {
      if (grid[r][c] === 2) q.push([r, c]);
      else if (grid[r][c] === 1) fresh++;
    }
  }
  if (fresh === 0) return 0;

  const dirs: [number, number][] = [[-1, 0], [1, 0], [0, -1], [0, 1]];
  let minutes = 0;
  while (q.length > 0) {
    const next: [number, number][] = [];
    for (const [r, c] of q) {
      for (const [dr, dc] of dirs) {
        const nr = r + dr, nc = c + dc;
        if (nr >= 0 && nr < R && nc >= 0 && nc < C && grid[nr][nc] === 1) {
          grid[nr][nc] = 2;
          fresh--;
          next.push([nr, nc]);
        }
      }
    }
    q = next;
    if (q.length > 0) minutes++;
  }
  return fresh === 0 ? minutes : -1;
}

const expect = (cond: boolean, msg = ""): void => { if (!cond) throw new Error("FAIL " + msg); };
const clone = (g: Grid): Grid => g.map((row) => row.slice());

const g1: Grid = [[2, 1, 1], [1, 1, 0], [0, 1, 1]];
const g2: Grid = [[2, 1, 1], [0, 1, 1], [1, 0, 1]];
const g3: Grid = [[0, 2]];
const g4: Grid = [[2, 2], [1, 1]];
expect(orangesRotting(clone(g1)) === 4, "4");
expect(orangesRotting(clone(g2)) === -1, "-1");
expect(orangesRotting(clone(g3)) === 0, "0");
expect(orangesRotting(clone(g4)) === 1, "1");
console.log("সব TS test pass!");

TS টীকা: q: [number, number][] ও dirs: [number, number][] — tuple type নিশ্চিত করে queue ও direction-এ ঠিক [row, col] জোড়াই থাকে, তাই destructuring ([r, c], [dr, dc]) type-safe। type Grid = number[][] cell value (0/1/2) সংখ্যা হিসেবে রাখে, তাই === 1/=== 2 তুলনা সঠিক type-এ হয়। return type number (-1 সহ) স্পষ্ট।

27. কোথায় কাজে লাগে (real-world use)

• Disease / fire / rumor spread: একসাথে অনেক উৎস থেকে কিছু ছড়ানোর simulation — কত ধাপে সবাই আক্রান্ত হবে, বা কেউ অরক্ষিত থেকে যাবে কিনা।
• Multi-source shortest distance: প্রতিটা cell থেকে নিকটতম একটা special source (hospital, exit, gate) পর্যন্ত দূরত্ব একসাথে বের করা।
• Network failure propagation: কয়েকটা failed node থেকে কত round-এ পুরো network প্রভাবিত হয়, বা কোনো অংশ বিচ্ছিন্ন থাকে কিনা।
• Heat / signal diffusion: একাধিক উৎস থেকে তাপ/সংকেত grid-এ কত ধাপে ছড়ায় তার মডেলিং।
• Game spread mechanics: আগুন/বিষ/দখল একসাথে অনেক জায়গা থেকে ছড়ানোর round-by-round হিসাব।

মূল সুর: "একসাথে অনেক জায়গা থেকে ছড়ায় / নিকটতম source পর্যন্ত কত ধাপ" — queue-টা সব source দিয়ে seed করো (multi-source BFS), level সংখ্যাই উত্তর; শেষে অপৌঁছনীয় কিছু বাকি থাকলে আলাদা সংকেত।

---

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