994. Rotting Oranges

At a Glance

Topic: Array
Pattern: Analyze Pattern
Difficulty: Medium
LeetCode: 994

Problem Statement

You are given an m x n grid where each cell can have one of three values:

0 representing an empty cell,
1 representing a fresh orange, or
2 representing a rotten orange.

Every minute, any fresh orange that is 4-directionally adjacent to a rotten orange becomes rotten.

Return the minimum number of minutes that must elapse until no cell has a fresh orange. If this is impossible, return -1.

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 Explanation: The orange in the bottom left corner (row 2, column 0) is never rotten, because rotting only happens 4-directionally.

Example 3:

Input: grid = [[0,2]] Output: 0 Explanation: Since there are already no fresh oranges at minute 0, the answer is just 0.

Constraints:

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

Approach & Solution Steps

DFS timestamp — messy with correctness — avoid.
Optimal — multi-source BFS — O(nm) time, O(nm) queue.

Optimal JS Solution

function orangesRotting(grid) {
  const rows = grid.length;
  const cols = grid[0].length;
  const queue = [];
  let fresh = 0;
  for (let row = 0; row < rows; row += 1) {
    for (let col = 0; col < cols; col += 1) {
      if (grid[row][col] === 2) {
        queue.push([row, col]);
      } else if (grid[row][col] === 1) {
        fresh += 1;
      }
    }
  }
  if (fresh === 0) {
    return 0;
  }
  const directions = [
    [1, 0],
    [-1, 0],
    [0, 1],
    [0, -1],
  ];
  let minutesElapsed = 0;
  let head = 0;
  while (queue.length - head > 0 && fresh > 0) {
    const waveCount = queue.length - head;
    for (let step = 0; step < waveCount; step += 1) {
      const cell = queue[head];
      head += 1;
      for (const [deltaRow, deltaCol] of directions) {
        const nextRow = cell[0] + deltaRow;
        const nextCol = cell[1] + deltaCol;
        if (nextRow < 0 || nextCol < 0 || nextRow >= rows || nextCol >= cols) {
          continue;
        }
        if (grid[nextRow][nextCol] !== 1) {
          continue;
        }
        grid[nextRow][nextCol] = 2;
        fresh -= 1;
        queue.push([nextRow, nextCol]);
      }
    }
    minutesElapsed += 1;
  }
  return fresh === 0 ? minutesElapsed : -1;
}

Edge Cases & Pitfalls

Always consider empty or null inputs.
Watch out for off-by-one index errors.