medium Rotting Oranges

Problem Statement

You are given an m x n matrix in which each cell can have one of three values:

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

At each minute, any fresh orange becomes rotten if it is 4-directionally adjacent to a rotten orange.

Return the minimum number of minutes that should be passed until all the orange gets rotten. If it is impossible, return -1.

Examples

• Input: grid =

[[2,1,0,0],
 [1,1,1,0],
 [0,1,1,1],
 [0,0,1,2]]

• Expected Output: 3
• Justification: The rotten oranges at (0,0) and (3,3) spread the rot to all adjacent fresh oranges. By day 4, all reachable fresh oranges are spoiled. The progression is as follows:
  • Minute 1: Oranges at positions (0, 1), (1, 0), (2, 3), and (3, 2) gets spoiled.
  • Minute 2: Oranges at positions (1, 1), and (2, 2) gets spoiled.
  • Minute 3: Oranges at positions (2, 1), and (1, 2) gets spoiled.

Example 2:

• Input: grid =

[[2,1,1],
 [1,1,0],
 [0,1,2]]

• Expected Output: 2
• Justification: The rotten oranges spread the rot to all fresh oranges in 2 minutes, successfully spoiling all of them.

Example 3:

• Input: grid =

[[0,2],
 [1,0],
 [0,1]]

• Expected Output: -1
• Justification: In any case, it is not possible that all oranges gets rotten.

Constraints:

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

Solution

To solve this problem, we'll use a breadth-first search (BFS) approach, treating the grid as a graph where each cell is a node connected to its adjacent (up, down, left, right) cells. This method is effective because it allows us to spread the rot from all rotten oranges simultaneously, day by day, mimicking the natural process of spoilage spreading. By tracking the days as levels in our BFS traversal, we can determine the minimum time required to spoil all reachable fresh oranges or identify if any remain unreachable and thus, unsolvable.

Our approach starts by identifying all the initial rotten oranges and adding them to a queue as the starting point of our BFS. We also count the number of fresh oranges to keep track of the progress. On each day (or level of BFS), we take the current rotten oranges from the queue, spoil their adjacent fresh oranges, and then add those newly rotten oranges to the queue for the next day's process. This continues until either there are no fresh oranges left or we cannot reach any more fresh oranges, indicating an unsolvable situation.

Step-by-Step Algorithm

1. Initialize a queue to keep track of the positions (row and column) of all initially rotten oranges. Also, maintain a counter to keep track of the number of fresh oranges present in the grid.

2. Iterate over the grid to find and add all initially rotten oranges' positions to the queue and count the number of fresh oranges. This step helps to understand the starting point of the problem and the goal to achieve (i.e., to rot all fresh oranges, if possible).

3. Perform a breadth-first search (BFS) from all initially rotten oranges simultaneously:

   • Increment a minute counter at the start of each level of BFS (each level represents a minute).
   • For each rotten orange in the queue, check its four adjacent cells (up, down, left, right). If an adjacent cell contains a fresh orange (denoted by 1), change it to a rotten orange (denoted by 2), decrement the fresh orange counter, and add its position to the queue for processing in the next minute.
   • Continue this process until the queue is empty or there are no more fresh oranges left to rot.

4. After the BFS completion, check if there are any fresh oranges left:

   • If no fresh oranges are left (fresh orange counter is 0), return the total minutes elapsed as the result.
   • If there are still fresh oranges left, return -1 to indicate that not all oranges can be rotted.

Algorithm Walkthrough

Initial Setup

• Grid:

  [[2,1,0,0],
   [1,1,1,0],
   [0,1,1,1],
   [0,0,1,2]]
  

• Rotten Oranges Queue: [(0,0), (3,3)] (positions of initially rotten oranges).
• Fresh Oranges Count: 8.

Minute 0: Start with two rotten oranges in the queue.

• Queue: [(0,0), (3,3)]
• Fresh Oranges: 8

Minute 1: Process the first level of the queue.

• Dequeue (0,0). It rots the oranges at positions (1,0) and (0,1).
• Dequeue (3,3). It rots the oranges at positions (2,3) and (3,2).
• New rotten oranges added to the queue: [(1,0), (0,1), (2,3), (3,2)].
• Grid After Minute 1:

  [[2,2,0,0],
   [2,1,1,0],
   [0,1,1,2],
   [0,0,2,2]]
  

• Fresh Oranges: 4

Minute 2: Process the second level of the queue.

• Dequeue and process (1,0), (0,1), (2,3), and (3,2). From these, only (1,0) and (2,3) have adjacent fresh oranges they can rot, specifically:
  • (0,1) directly rots (1,1).
  • (1,0) has no more fresh oranges to rot adjacent to it.
  • (2,3) rots (2,2).
  • (3,2) has no more fresh oranges to rot adjacent to it.
• New rotten oranges added to the queue: [(1,1), (2,2)].
• Grid After Minute 2:

  [[2,2,0,0],
   [2,2,1,0],
   [0,1,2,2],
   [0,0,2,2]]
  

• Fresh Oranges: 2

Minute 3: Process the third level of the queue.

• Dequeue and process (1,1) and (2,2). These new rotten oranges can rot the remaining fresh oranges at (2,1) and (1,2).
• New rotten oranges added to the queue: [(2,1), (1,2)].
• Grid After Minute 3:

  [[2,2,0,0],
   [2,2,2,0],
   [0,2,2,2],
   [0,0,2,2]]
  

• Fresh Oranges: 0

Conclusion: By the end of Minute 3, all reachable fresh oranges have been spoiled, and the grid no longer contains any fresh oranges.

Code

import java.util.LinkedList;
import java.util.Queue;

class Solution {

  public int orangesRotting(int[][] grid) {
    if (grid == null || grid.length == 0) return -1;
    int rows = grid.length, cols = grid[0].length;
    Queue<int[]> queue = new LinkedList<>();
    int freshOranges = 0;

    // Step 1: Find all rotten oranges and count fresh oranges
    for (int i = 0; i < rows; i++) {
      for (int j = 0; j < cols; j++) {
        if (grid[i][j] == 2) {
          queue.offer(new int[] { i, j });
        } else if (grid[i][j] == 1) {
          freshOranges++;
        }
      }
    }

    if (freshOranges == 0) return 0; // No fresh oranges to rot
    int minutes = 0;
    int[][] directions = { { 0, 1 }, { 1, 0 }, { -1, 0 }, { 0, -1 } };

    // Step 2: BFS to rot all reachable fresh oranges
    while (!queue.isEmpty()) {
      minutes++;
      int size = queue.size();

      for (int i = 0; i < size; i++) {
        int[] point = queue.poll();
        for (int[] dir : directions) {
          int x = point[0] + dir[0];
          int y = point[1] + dir[1];

          if (x >= 0 && y >= 0 && x < rows && y < cols && grid[x][y] == 1) {
            grid[x][y] = 2; // Rot the orange
            freshOranges--;
            queue.offer(new int[] { x, y });
          }
        }
      }
    }

    // Step 3: Check if any fresh orange is left
    return freshOranges == 0 ? minutes - 1 : -1;
  }

  public static void main(String[] args) {
    Solution solution = new Solution();
    // Example 1
    int[][] grid1 = {
      { 2, 1, 0, 0 },
      { 1, 1, 1, 0 },
      { 0, 1, 1, 1 },
      { 0, 0, 1, 2 },
    };
    System.out.println(solution.orangesRotting(grid1));

    // Example 2
    int[][] grid2 = { { 2, 1, 1 }, { 1, 1, 0 }, { 0, 1, 2 } };
    System.out.println(solution.orangesRotting(grid2));

    // Example 3
    int[][] grid3 = { { 0, 2 }, { 1, 0 }, { 0, 1 } };
    System.out.println(solution.orangesRotting(grid3));
  }
}

Complexity Analysis

• Time Complexity: The time complexity is , where (M) and (N) are the dimensions of the grid. This is because, in the worst case, each cell is visited at least once.
• Space Complexity: The space complexity is in the worst case due to the queue potentially holding all the oranges if they are all rotten initially.