Rotting Oranges

Examples

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

Rot spreads outward from the single rotten orange in the top-left, reaching the farthest fresh orange after 4 minutes.

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

The fresh orange in the bottom-left corner is boxed in by 0s on every side it could rot from, so it can never turn rotten.

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

There are no fresh oranges to begin with, so 0 minutes are needed.

Constraints

• 1 <= rows, cols <= 10

• grid[i][j] is 0, 1, or 2

Approach

The phrase "every rotten orange spreads to its neighbors at the same time" is the giveaway: this calls for a multi-source breadth-first search - a BFS that starts from every rotten orange at once instead of just one starting point.

Load every rotten orange into a queue to begin with (this represents minute 0). Then repeatedly process the queue in layers: pop each cell currently in the queue, rot any fresh neighbor it has, and push those newly-rotten cells on for the next layer. Because BFS naturally processes cells one "ring" of distance at a time, each full layer you process corresponds to exactly one minute passing - so the number of layers it takes to rot everything reachable is the answer.

After the BFS finishes, if any fresh orange is still left, it was never reachable, so the answer is -1.

Solutions

Brute Force - Simulate Minute by Minute

Repeatedly scan the whole grid looking for rotten oranges, collect every fresh orange adjacent to one, then rot all of them together (this represents one minute passing). Keep going until either no fresh oranges remain, or a full scan finds nothing new to rot (meaning whatever fresh oranges are left are unreachable).

function orangesRotting(grid) {
  const rows = grid.length;
  const cols = grid[0].length;
  let minutes = 0;

  function hasFreshOrange() {
    for (let r = 0; r < rows; r++) {
      for (let c = 0; c < cols; c++) {
        if (grid[r][c] === 1) return true;
      }
    }
    return false;
  }

  while (hasFreshOrange()) {
    const toRot = [];

    for (let r = 0; r < rows; r++) {
      for (let c = 0; c < cols; c++) {
        if (grid[r][c] !== 2) continue;

        const neighbors = [[r + 1, c], [r - 1, c], [r, c + 1], [r, c - 1]];
        for (const [nr, nc] of neighbors) {
          if (nr >= 0 && nr < rows && nc >= 0 && nc < cols && grid[nr][nc] === 1) {
            toRot.push([nr, nc]);
          }
        }
      }
    }

    if (toRot.length === 0) {
      return -1; // fresh oranges remain, but nothing new rotted this minute
    }

    for (const [r, c] of toRot) {
      grid[r][c] = 2;
    }
    minutes++;
  }

  return minutes;
}

Time: O((rows × cols)²) in the worst case · Space: O(rows × cols)

Optimal - Multi-Source BFS

Start a BFS queue loaded with every rotten orange at once, and track how many fresh oranges exist. Process the queue: for each rotten orange popped, rot any fresh neighbor, decrement the fresh count, and push that neighbor onto the queue tagged with the minute it rotted. The last minute assigned this way is the answer - unless fresh oranges remain once the queue empties, in which case it's -1.

function orangesRotting(grid) {
  const rows = grid.length;
  const cols = grid[0].length;
  const queue = [];
  let freshCount = 0;

  for (let r = 0; r < rows; r++) {
    for (let c = 0; c < cols; c++) {
      if (grid[r][c] === 2) {
        queue.push([r, c, 0]);
      } else if (grid[r][c] === 1) {
        freshCount++;
      }
    }
  }

  if (freshCount === 0) return 0;

  let minutes = 0;

  while (queue.length > 0) {
    const [r, c, time] = queue.shift();
    const neighbors = [[r + 1, c], [r - 1, c], [r, c + 1], [r, c - 1]];

    for (const [nr, nc] of neighbors) {
      if (nr >= 0 && nr < rows && nc >= 0 && nc < cols && grid[nr][nc] === 1) {
        grid[nr][nc] = 2;
        freshCount--;
        minutes = time + 1;
        queue.push([nr, nc, time + 1]);
      }
    }
  }

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

Time: O(rows × cols) · Space: O(rows × cols)