Rotting Oranges

Share

Find minimum time for all oranges to rot. Rotten oranges spread to adjacent fresh ones each minute.

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

Solution Approach

Multi-source BFS from all initially rotten oranges. Count minutes and fresh oranges remaining.

  • Add all rotten orange positions to BFS queue, count fresh oranges
  • BFS layer by layer (each layer = 1 minute)
  • For each rotten orange: rot adjacent fresh oranges, decrement fresh count
  • After BFS: if fresh > 0 return -1, else return minutes
Java
public int orangesRotting(int[][] grid) {
    int m = grid.length, n = grid[0].length, fresh = 0, minutes = 0;
    Queue<int[]> queue = new LinkedList<>();
    for (int i = 0; i < m; i++) for (int j = 0; j < n; j++) {
        if (grid[i][j] == 2) queue.add(new int[]{i, j});
        else if (grid[i][j] == 1) fresh++;
    }
    int[][] dirs = {{0,1},{0,-1},{1,0},{-1,0}};
    while (!queue.isEmpty() && fresh > 0) {
        minutes++;
        for (int size = queue.size(); size > 0; size--) {
            int[] cur = queue.poll();
            for (int[] d : dirs) {
                int ni = cur[0]+d[0], nj = cur[1]+d[1];
                if (ni>=0 && ni<m && nj>=0 && nj<n && grid[ni][nj]==1) {
                    grid[ni][nj]=2; fresh--; queue.add(new int[]{ni,nj});
                }
            }
        }
    }
    return fresh == 0 ? minutes : -1;
}
  • Time Complexity: O(m*n)
  • Space Complexity: O(m*n)