Rotten Oranges

Time: O(n*m)

Space: O(n*m)

Intuition

Multi-source BFS: add all initially rotten oranges to the queue. Each BFS step represents one minute of rotting. After BFS, if any fresh orange remains, return -1.

Algorithm

1Count fresh oranges. Enqueue all rotten (value=2) cells with time=0.
2BFS: dequeue (r,c,t). For each 4-neighbor: if fresh: mark rotten, fresh--, enqueue with t+1.
3If fresh==0: return maxTime. Else: return -1.

Example Walkthrough

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

1.Start: rotten at (0,0). Minute 1: (0,1),(1,0) rot. Minute 2: (0,2),(1,1) rot. Minute 3: (2,1) rots. Minute 4: (2,2) rots.
2.Total=4.

Output: 4

Common Pitfalls

•Start BFS with ALL rotten oranges simultaneously â€” not from just one source.

Rotten Oranges.java

Java

// Approach: Multi-source BFS from all initially rotten oranges. Track time steps to rot all fresh oranges.
// Time: O(n*m) Space: O(n*m)
import java.util.*;

class Solution {
    public int orangesRotting(int[][] mat) {
        if (mat == null || mat.length == 0)
            return -1;

        int n = mat.length;
        int m = mat[0].length;
        Queue<int[]> queue = new LinkedList<>();
        int freshCount = 0;
        int time = 0;

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (mat[i][j] == 2)
                    queue.add(new int[] { i, j, 0 });
                else if (mat[i][j] == 1)
                    freshCount++;
            }
        }

        if (freshCount == 0)
            return 0;

        int[] dRow = { -1, 1, 0, 0 };
        int[] dCol = { 0, 0, -1, 1 };

        while (!queue.isEmpty()) {
            int[] cell = queue.poll();
            int i = cell[0], j = cell[1], currTime = cell[2];
            time = Math.max(time, currTime);

            for (int d = 0; d < 4; d++) {
                int ni = i + dRow[d], nj = j + dCol[d];

                if (ni >= 0 && ni < n && nj >= 0 && nj < m && mat[ni][nj] == 1) {
                    mat[ni][nj] = 2;
                    freshCount--;
                    queue.add(new int[] { ni, nj, currTime + 1 }); // Add to queue with new time
                }
            }
        }

        return freshCount == 0 ? time : -1;
    }
}

Was this solution helpful?