Rotting Oranges

MediumBFS Matrix Graph

A fruit wholesaler packs oranges into a tray of m × n slots, described by grid, where each slot holds one of three values:

0: the slot is empty,
1: the slot holds a fresh orange,
2: the slot holds a rotten orange.

Rot spreads once a minute: at the end of each minute, every fresh orange directly above, below, left or right of a rotten orange turns rotten too. Empty slots stop the spread.

Return how many minutes pass before no fresh orange is left in the tray. If some fresh orange can never be reached by the rot, return -1. If the tray starts with no fresh oranges, return 0.

Example 1

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

Explanation: The rot creeps along the bottom row, up the right-hand column and back along the top row, one slot per minute.

Example 2

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

Explanation: Empty slots wall off the two fresh oranges on the right.

Example 3

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

Explanation: There are no fresh oranges, so no time needs to pass.

Constraints

The tray has between 1 and 10 rows and between 1 and 10 columns.
Every slot holds 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