63. Rotting Oranges

A crate is modelled as an m × n grid where each cell holds:

0: an empty spot,
1: a fresh orange,
2: a rotten orange.

Every minute, each fresh orange that is horizontally or vertically next to a rotten orange becomes rotten itself.

Return the number of minutes that pass until no fresh orange is left. If some fresh orange can never rot, return -1. If there are no fresh oranges to begin with, the answer is 0.

Example 1

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

Explanation: The rot spreads right and down in minute 1, reaches the centre in minute 2, then the bottom middle in minute 3 and the bottom-right orange in minute 4.

Example 2

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

Explanation: The empty cell separates the fresh orange from the rotten one.

Example 3

Input: grid = [[0,0],[0,0]]
Output: 0

Constraints

1 <= m, n <= 10
grid[i][j] is 0, 1 or 2

💡 Hint 1

All rotten oranges spread at the same time, so treat them all as starting points of one search.

💡 Hint 2

A multi-source BFS processes the grid one "minute" (one BFS level) at a time.

💡 Hint 3

Count the fresh oranges first. Each time one rots, decrement the count; if it is not zero when the BFS ends, return -1.

Try it yourself first ✎

Solutions stick better after a real attempt. Peek when you're ready.

Approach

Multi-source BFS. Put every initially rotten orange in the queue and count the fresh ones. Process the queue one level at a time: each level is one minute, and every fresh neighbour of a cell in the current level turns rotten and joins the next level. Stop when a level adds nothing or no fresh oranges remain. The number of levels that rotted something is the answer, unless fresh oranges are still left, in which case return -1.

Time O(m · n)Space O(m · n)

function orangesRotting(grid) {
  const rows = grid.length;
  const cols = grid[0].length;
  let fresh = 0;
  let queue = [];
  for (let r = 0; r < rows; r++) {
    for (let c = 0; c < cols; c++) {
      if (grid[r][c] === 2) queue.push([r, c]);
      else if (grid[r][c] === 1) fresh++;
    }
  }
  let minutes = 0;
  while (queue.length && fresh > 0) {
    const next = [];
    for (const [r, c] of queue) {
      for (const [y, x] of [[r + 1, c], [r - 1, c], [r, c + 1], [r, c - 1]]) {
        if (y >= 0 && y < rows && x >= 0 && x < cols && grid[y][x] === 1) {
          grid[y][x] = 2;
          fresh--;
          next.push([y, x]);
        }
      }
    }
    queue = next;
    minutes++;
  }
  return fresh === 0 ? minutes : -1;
}

class Solution {
    public int orangesRotting(int[][] grid) {
        int rows = grid.length, cols = grid[0].length, fresh = 0;
        Deque<int[]> queue = new ArrayDeque<>();
        for (int r = 0; r < rows; r++) {
            for (int c = 0; c < cols; c++) {
                if (grid[r][c] == 2) queue.add(new int[] { r, c });
                else if (grid[r][c] == 1) fresh++;
            }
        }
        int[][] dirs = { { 1, 0 }, { -1, 0 }, { 0, 1 }, { 0, -1 } };
        int minutes = 0;
        while (!queue.isEmpty() && fresh > 0) {
            for (int size = queue.size(); size > 0; size--) {
                int[] cell = queue.poll();
                for (int[] d : dirs) {
                    int y = cell[0] + d[0], x = cell[1] + d[1];
                    if (y >= 0 && y < rows && x >= 0 && x < cols && grid[y][x] == 1) {
                        grid[y][x] = 2;
                        fresh--;
                        queue.add(new int[] { y, x });
                    }
                }
            }
            minutes++;
        }
        return fresh == 0 ? minutes : -1;
    }
}

/**
 * @param {number[][]} grid
 * @return {number}
 */
function orangesRotting(grid) {

}

Ctrl/⌘ + ' run · Ctrl/⌘ + Enter submit