Solution: Rotting Oranges

Statement#

Consider an $m \times n$ grid containing cells with three potential values:

• $0$, which indicates an unoccupied cell.

• $1$, representing a freshly picked orange.

• $2$, indicating a rotten orange.

Any fresh orange that is 4–directionally adjacent to a rotten orange will also turn rotten with each passing minute.

Your task is to determine the minimum time required for all cells to have rotten oranges. In case, this objective cannot be achieved, return $-1$.

Constraints:

• m $=$ grid.length

• n $=$ grid[i].length

• $1$ $\leq$ m, n $\leq$ $10$

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

Solution#

Let’s solve this problem by understanding the nature of the problem first. We are asked to find the minimum time required for all the cells to have rotten oranges. As proposed in the problem statement, the 4–directionally adjacent cells in the grid will rot first. We can think of the rotten oranges as the root nodes and the fresh oranges in other cells as their neighbors. Thus, we can limit our choice for solving this problem using the breadth-first search approach because the rotten oranges will contaminate the neighbor oranges first and then move to the next neighbors in the graph.

We can visualize the rotting procedure of oranges in the grid by having a look at the following illustration:

The illustration above shows that each orange acts as a root because the adjacent cells/oranges directly connected to the root orange are affected first. As we traverse through the grid from the top–left cell to the cells on the right, all the other connected oranges begin to rot. This process is similar to level-order traversal. To solve this problem, we use the queue data structure to keep track of the candidate nodes we need to visit during the process.

Here’s how to algorithm works:

• Storing the rotten oranges and counting the fresh oranges:

  • We’ll iterate through the grid of oranges, and whenever we find a rotten orange (denoted by 2), we add it to the rotten_queue. Otherwise, if we encounter any fresh orange (denoted by 1), we increment the counter, fresh_oranges, by 1.

• Process of rotting oranges and counting minutes elapsed:

  • While there are rotten oranges in the rotten_queue, we’ll process them in batches based on the current minute of the orange (this is denoted by the level of that orange in that graph).

    • We’ll check the neighboring cells for each rotten orange in all four directions.

      • If a neighboring cell contains a fresh orange, we’ll mark it rotten by changing its value from 1 to 2, and the fresh_oranges count is decremented.

      • The coordinates of the newly rotten orange will be added to the rotten_queue for the next minute’s processing.

      • We’ll use the minutes variable to increment with each minute of processing.

After the “Process of rotting oranges and counting minutes elapsed” is completed, there are two possible outcomes:

• If there are still fresh oranges left (fresh_oranges > 0), it means not all oranges can be rotten, so -1 is returned.

• Otherwise, the maximum of 0 and minutes - 1 is returned, indicating the time it took to rot all the oranges.

In the graph below, we have illustrated how the rotting process happens as we propagate through the layers, one level at a time:

Let’s have a look at the code for the algorithm we just discussed:

Time complexity#

The time complexity of the above is $O(m \times n)$, where $m$ is the number of rows, and $n$ is the number of columns in the grid.

1. The for loop iterates through the entire grid of size $rows \times cols$ to identify the initial rotten oranges and count the fresh oranges. This initial loop has a time complexity of $O(m \times n)$.

2. Then, it enters a while loop that continues until there are no more fresh oranges left or until all possible rotten oranges have been processed. In the worst case, every fresh orange needs to be rotten, so this loop can iterate at most $rows \times cols$ times, which is $O(m \times n)$.

   1. Inside the while loop, for each rotten orange, it checks its neighboring oranges. In the worst case, it can have 4 neighbors (up, down, left, right), and for each neighbor, it performs constant time operations (checks and updates). So, the operations inside the loop can be considered $O(1)$.

Overall, the time complexity of the code is $O(m \times n)$ for the initial loop plus $O(m \times n)$ for the while loop (in the worst case), which simplifies to $O(m \times n)$.

Space complexity#

The space complexity is $O(m \times n)$ as we use a queue to store the positions of oranges, and in the worst case, all oranges may be added to the queue.