LeetCode Study Note | Problem 994: Rotting Oranges

🔍 Problem Overview

You’re given an m x n grid, where:

• 0 represents an empty cell

• 1 represents a fresh orange

• 2 represents a rotten orange

Each minute, any rotten orange will cause adjacent (up/down/left/right) fresh oranges to rot.

Goal: Return the minimum number of minutes needed for all fresh oranges to become rotten. If it’s impossible, return -1.

🧠 When to Use BFS?

We often choose between DFS and BFS for traversal problems. They have different use cases:

💡 Why BFS Here?

• BFS explores nodes level by level, i.e., distance = 0 → 1 → 2 → …

• The first time we reach a node is always the shortest distance from the source.

• This aligns with the idea of minutes passing by in waves of rot.

In this problem, the rotting process is essentially a multi-source shortest path problem, where all the initially rotten oranges are sources, and the goal is to infect all reachable fresh oranges in the minimum amount of time.

So — BFS is a natural fit ✅

🧱 BFS Template for Shortest Path Problems

Basic BFS:

while queue is not empty:
    node = queue.pop()
    for neighbor in node's neighbors:
        if neighbor not visited:
            queue.append(neighbor)

Layered BFS (for shortest path or level tracking):

depth = 0
while queue is not empty:
    depth += 1
    size = len(queue)
    for i in range(size):
        node = queue.pop()
        for neighbor in node's neighbors:
            if neighbor not visited:
                queue.append(neighbor)

Key idea: Process nodes level-by-level, so each “layer” corresponds to one time unit (e.g., 1 minute in this problem).

🍊 Applying BFS to This Problem

Steps:

1. Initialize:

   • Count all fresh oranges.

   • Put all initially rotten oranges into a queue (multi-source BFS).

2. Run BFS:

   • For each minute, process all rotten oranges currently in the queue.

   • Infect adjacent fresh oranges, update the grid, reduce fresh orange count, and enqueue the newly rotten ones.

3. End condition:

   • If all fresh oranges are rotten → return the number of rounds (minutes).

   • If there are still fresh oranges left → return -1.

💻 Java Implementation

public int orangesRotting(int[][] grid) {
    int M = grid.length;
    int N = grid[0].length;
    Queue<int[]> queue = new LinkedList<>();

    int count = 0; // count fresh orange
    for (int r = 0; r < M; r++) {
        for (int c = 0; c < N; c++) {
            if (grid[r][c] == 1) {
                count++;
            } else if (grid[r][c] == 2) {
                queue.add(new int[]{r, c});
            }
        }
    }

    int round = 0; 
    while (count > 0 && !queue.isEmpty()) {
        round++;
        int n = queue.size();
        for (int i = 0; i < n; i++) {
            int[] orange = queue.poll();
            int r = orange[0];
            int c = orange[1];

            if (r - 1 >= 0 && grid[r - 1][c] == 1) {
                grid[r - 1][c] = 2;
                count--;
                queue.add(new int[]{r - 1, c});
            }
            if (r + 1 < M && grid[r + 1][c] == 1) {
                grid[r + 1][c] = 2;
                count--;
                queue.add(new int[]{r + 1, c});
            }
            if (c - 1 >= 0 && grid[r][c - 1] == 1) {
                grid[r][c - 1] = 2;
                count--;
                queue.add(new int[]{r, c - 1});
            }
            if (c + 1 < N && grid[r][c + 1] == 1) {
                grid[r][c + 1] = 2;
                count--;
                queue.add(new int[]{r, c + 1});
            }
        }
    }

    return count == 0 ? round : -1;
}

✅ Key Insights

• Treat each minute as one layer of BFS.

• Each level of BFS spreads the rot further.

• By tracking count of fresh oranges, we avoid unnecessary full-grid scans.

• This is a textbook case of BFS for shortest-path/time-infection spread.