Coding Interview Questions | Rotting Oranges

January 21st, 2024

Rotting Oranges Problem Introduction:

This summary will talk about my solution to the rotting oranges problem as seen on leetcode here. A synopsis of the problem summary will be shown below:

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.

How do you solve the Rotting Oranges Problem using Breadth-First Search?

Solution:

function orangesRotting(grid: number[][]): number {
  const visited = Array.from({ length: grid.length }, () =>
    Array.from({ length: grid[0].length }, () => false)
  );

  // Original stack has locations of rotting oranges only
  const nodeStack: { row: number; col: number; depth: number }[] = [];

  for (let rowIdx = 0; rowIdx < grid.length; rowIdx++) {
    for (let colIdx = 0; colIdx < grid[rowIdx].length; colIdx++) {
      const val = grid[rowIdx][colIdx];

      if (val === 0) {
        visited[rowIdx][colIdx] = true;
      }

      if (val === 2) {
        nodeStack.push({ col: colIdx, row: rowIdx, depth: 0 });
      }
    }
  }

  const directions: { hor: number; vert: number }[] = [
    { hor: 0, vert: 1 },
    { hor: 0, vert: -1 },
    { hor: 1, vert: 0 },
    { hor: -1, vert: 0 },
  ];
  const MAX_ROWS = grid.length;
  const MAX_COLS = grid[0].length;
  let maxDepth = 0;

  while (nodeStack.length > 0) {
    const currentNode = nodeStack.shift()!;
    if (visited[currentNode.row][currentNode.col]) {
      continue;
    }
    visited[currentNode.row][currentNode.col] = true;

    // Update the maximum amount of time it takes the oranges to rot
    // if current orange time exceeds previous max time
    if (currentNode.depth > maxDepth) {
      maxDepth = currentNode.depth;
    }

    for (const dir of directions) {
      const { hor, vert } = dir;
      const nextRow = currentNode.row + vert;
      const nextCol = currentNode.col + hor;

      // Add fresh oranges to be visited next if they're 4-directionally adjacent to a rotting orange, a valid square in the
      // grid and have not been visited yet
      if (
        nextRow >= 0 &&
        nextRow < MAX_ROWS &&
        nextCol >= 0 &&
        nextCol < MAX_COLS &&
        grid[nextRow][nextCol] === 1 &&
        !visited[nextRow][nextCol]
      ) {
        nodeStack.push({
          col: nextCol,
          row: nextRow,
          depth: currentNode.depth + 1,
        });
      }
    }
  }

  const allRotten = visited.every((row) => row.every((entry) => entry));

  return allRotten ? maxDepth : -1;
}

Oranges Rotting Solution Summary:

Below is a breakdown of the key aspects of the solution above for the rotting oranges problem:

1. Initialization and Stack Setup: We first initialize a 2D array visited to keep track of visited cells in the grid. A stack nodeStack is also created to store the locations of initially rotting oranges.

2. Iterative Processing: The algorithm initially iterates through the grid, marking empty cells as visited and pushing locations of rotting oranges onto the stack.

3. Directional Movement: Four directional movements (up, down, left, right) are defined for exploration using the directions array.

4. Breadth-First Search: We employ a breadth-first search approach, continuously updating the depth (time) it takes for oranges to rot.

5. Fresh Orange Processing: Fresh oranges adjacent to rotting oranges are added to the stack for future processing, considering grid boundaries and unvisited status.

6. Result Calculation: The algorithm determines if all cells are visited, indicating that all oranges have rotted, and returns the maximum depth as the result. If not, it returns -1.

Complexities

1. Time Complexity: The time complexity is influenced by the breadth-first search and the grid dimensions. Denoted as O(n * m), where n is the number of rows and m is the number of columns.

2. Space Complexity: The space complexity is determined by the storage of the visited array and the stack. It is O(n * m) due to the usage of the grid dimensions.