994. Rotting Oranges

Problem Description

This problem presents a scenario where we have a grid that represents a box of oranges. The oranges can either be fresh (represented by 1), rotten (2), or the cell can be empty (0). The challenge is to find out how long it will take for all fresh oranges to become rotten given that each minute, every fresh orange that is adjacent (up, down, left, or right) to a rotten orange will become rotten itself. If it's impossible for all oranges to become rotten (e.g., if some oranges are unreachable by the rotten ones), we are to return -1.

The problem expects us to determine the minimum number of minutes that must pass until there are no fresh oranges left or to assert that such a state is impossible to achieve.

Intuition

The intuition behind the solution is to use a Breadth-First Search (BFS) approach, which is well-suited for problems involving levels or minutes passing by as in this case. We can think of each minute as a level in a BFS traversal.

The process begins by scanning the grid to do two things:

1. Identify and enqueue all the initially rotten oranges (cells with a value 2), as these will be the starting points for the spread of rot, and
2. Count the amount of fresh oranges (cells with a value 1) because we need to keep track of when no fresh oranges are left.

The solution proceeds in rounds, where each round represents one minute. In each round, the solution:

• Increments the time counter once for all rotten oranges that will affect fresh ones in that minute.
• Dequeues a location of a rotten orange and checks its 4-directional neighbors.
• If a neighbor is a fresh orange, it becomes rotten. We decrement the count of fresh oranges and enqueue the new rotten orange's location for the next round of processing.

If there are no more fresh oranges (cnt = 0), the BFS is complete, and the time counter (ans) reflects the minimum number of minutes elapsed. If some fresh oranges were never reached (and therefore cnt is not zero after the BFS), it's impossible to rot all oranges, and the function returns -1.

Learn more about Breadth-First Search patterns.

Solution Approach

The implementation of the solution starts by initializing some basic variables:

• m, n to store the dimensions of the grid.
• q, a double-ended queue (deque), which is used to perform efficient pop and append operations from both ends, crucial for BFS.
• cnt to keep a count of the fresh oranges.

Next, we iterate through the grid to fill our queue q with the initial positions of the rotten oranges and count the number of fresh oranges using cnt. This setup phase is necessary to kickstart the BFS process.

Now, we define a variable ans to keep track of the time taken in minutes. We execute a loop that continues as long as there are fresh oranges (cnt) and there are rotten oranges in the queue to process (q). Each iteration of the loop represents a passing minute where potential rotting of adjacent oranges occurs.

Inside the loop, we increment ans for each round of minute and process all rotten oranges in the queue for that minute:

• Pop each position of a rotten orange from the front of the queue.
• Look at each of the four adjacent cells using the provided direction vectors [[0, 1], [0, -1], [1, 0], [-1, 0]].
• For each adjacent cell:
  • Calculate the new coordinates x and y based on the current position i, j and the direction vector a, b.
  • Check if the adjacent cell is within the grid bounds and if it contains a fresh orange (grid[x][y] == 1).
  • If the adjacent cell is a fresh orange, decrement cnt, set that cell to 2 (rotten), and append its position to the queue q for processing in the next minute.

Once the BFS loop ends, we check whether there are any fresh oranges left untouched (cnt > 0). If there are, we return -1, indicating that it's impossible to rot all oranges. If cnt is 0, meaning all fresh oranges have been turned rotten, we return ans, the total minutes elapsed.

The use of BFS ensures that we process all oranges that could potentially become rotten in a particular minute before moving on to the next minute. This closely emulates the passage of time and the spread of rot from orange to orange. The deque data structure allows us to efficiently enqueue new rotten oranges for subsequent processing while still keeping track of the current round of oranges being processed.

Example Walkthrough

Let's consider a 3x3 grid of oranges to illustrate the solution approach:

12 1 0
21 1 0
30 0 1

In this example:

• 2 represents a rotten orange.
• 1 represents a fresh orange.
• 0 represents an empty cell.

First, we initialize our variables:

• m is 3 (number of rows).
• n is 3 (number of columns).
• q is an empty queue that will contain the positions of rotten oranges.
• cnt is a count of fresh oranges, which we initialize to 0 and will increment as we find fresh oranges.
• ans is initialized to -1, so if we do not find any fresh oranges, we will return -1.

We scan the grid and find that there is one rotten orange at position (0,0), and there are three fresh oranges. We add the position of the rotten orange to q and increment cnt as we count fresh oranges.

Now the queue q and cnt are as follows:

• q contains [(0, 0)]
• cnt is 3 (as there are 3 fresh oranges)

Next, we set ans to 0 as we prepare to simulate time passing.

Now, we begin our BFS loop. Since q is not empty and cnt is not zero, we proceed:

• As we enter the loop, we increment ans to represent the first minute passing.
• We dequeue (0, 0) from q and examine its neighbors (0, 1), (1, 0), as only these two are within the bounds of the grid and adjacent to it.
• Neighbor (0, 1) is a fresh orange, so we set it to rotten (grid[0][1] = 2), decrement cnt to 2, and enqueue (0, 1) for the next round.
• Neighbor (1, 0) is fresh as well, we perform the same operation: set it to rotten, decrement cnt to 1, and enqueue (1, 0).

The grid now looks like this:

12 2 0
22 1 0
30 0 1

And q has [(0, 1), (1, 0)] with ans being 1.

We enter the second minute:

• Increment ans to 2.
• We have two positions in q to process: (0, 1) and (1, 0).
• From (0, 1), we look at its neighbors, but none are fresh oranges.
• From (1, 0), we look at neighbor (1, 1) which is fresh and make it rotten, decrement cnt to 0, and enqueue (1, 1).

Now the grid and variables are:

12 2 0
22 2 0
30 0 1

• q contains [(1, 1)]
• cnt is 0 (no more fresh oranges)
• ans is 2.

Now we have processed all fresh oranges, so we exit the BFS loop and return ans, which is 2. This is the minimum number of minutes until there are no fresh oranges left. The last orange at (2, 2) could never become rotten as it's not adjacent to any rotten or potentially rotting oranges, so it is not counted.

Solution Implementation

Time and Space Complexity

Time Complexity

The time complexity of the code is O(M * N), where M is the number of rows and N is the number of columns in the grid. This is because in the worst case, we may have to look at each cell in the grid. The while loop runs until all the rotten oranges have been processed. In the worst case, processing one rotten orange could affect 4 adjacent cells, but each cell is enqueued and dequeued only once. This gives us the worst-case scenario of processing M * N cells.

Space Complexity

The space complexity of the code is also O(M * N). This is due to the queue which in the worst case might need to store all the cells if they are all rotten oranges. In addition to the queue, we have constant space for the variables m, n, cnt, and ans, but they do not scale with the size of the input, so the dominating factor is the space needed for the queue.

Learn more about how to find time and space complexity quickly using problem constraints.