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.

Flowchart Walkthrough

For leetcode 994. Rotting Oranges, we can use the Flowchart to determine the appropriate algorithm. Here's a detailed walk-through based on the provided flowchart:

Is it a graph?

  • Yes: The grid in the problem can be interpreted as a graph, where each cell is a node. Adjacent cells are connected by edges.

Is it a tree?

  • No: The graph might contain cycles (oranges can rot back and forth in adjacencies), so it doesn’t strictly form a hierarchical tree structure.

Is the problem related to directed acyclic graphs (DAGs)?

  • No: Direction does not play a role in the spreading of decay, and cyclic dependencies are not a concern in this problem.

Is the problem related to shortest paths?

  • Yes: The core of the problem is to determine the minimum time (shortest path in terms of time steps) required for all fresh oranges to become rotten, if possible.

Is the graph weighted?

  • No: Each movement or time step from one orange to an adjacent one takes the same amount of time; hence, the graph is unweighted.

Conclusion: Based on the flowchart, for an unweighted shortest path problem, BFS (Breadth-First Search) is the most suitable algorithm since it explores each level or layer (each minute in this context) uniformly, hence determining the minimum time required efficiently.

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.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

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

1from collections import deque
2
3class Solution:
4    def orangesRotting(self, grid: List[List[int]]) -> int:
5        # Get the number of rows and columns of the grid.
6        rows, cols = len(grid), len(grid[0])
7
8        # Initialize a queue for BFS and a counter for fresh oranges.
9        queue = deque()
10        fresh_count = 0
11      
12        # Go through each cell in the grid.
13        for i in range(rows):
14            for j in range(cols):
15                # If we find a rotten orange, add its position to the queue.
16                if grid[i][j] == 2:
17                    queue.append((i, j))
18                # If it's a fresh orange, increment the fresh_count.
19                elif grid[i][j] == 1:
20                    fresh_count += 1
21      
22        # Track the number of minutes passed.
23        minutes_passed = 0
24      
25        # Perform BFS until the queue is empty or there are no fresh oranges left.
26        while queue and fresh_count > 0:
27            # Increment minutes each time we start a new round of BFS.
28            minutes_passed += 1
29          
30            # Loop over all the rotten oranges at the current minute.
31            for _ in range(len(queue)):
32                i, j = queue.popleft()
33              
34                # Check the adjacent cells in all four directions.
35                for delta_row, delta_col in [[0, 1], [0, -1], [1, 0], [-1, 0]]:
36                    x, y = i + delta_row, j + delta_col
37                  
38                    # If the adjacent cell has a fresh orange, rot it.
39                    if 0 <= x < rows and 0 <= y < cols and grid[x][y] == 1:
40                        fresh_count -= 1
41                        grid[x][y] = 2
42                        queue.append((x, y))
43      
44        # If there are no fresh oranges left, return the minutes passed.
45        # Otherwise, return -1 because some oranges will never rot.
46        return minutes_passed if fresh_count == 0 else -1
47
1class Solution {
2    public int orangesRotting(int[][] grid) {
3        int rows = grid.length, cols = grid[0].length;
4        int freshOranges = 0; // Counter for fresh oranges
5        Deque<int[]> queue = new LinkedList<>(); // Queue for rotten oranges' positions
6      
7        // Preprocess the grid, enqueue all rotten oranges and count the fresh ones
8        for (int i = 0; i < rows; ++i) {
9            for (int j = 0; j < cols; ++j) {
10                if (grid[i][j] == 2) { // If orange is rotten
11                    queue.offer(new int[] {i, j});
12                } else if (grid[i][j] == 1) { // If orange is fresh
13                    freshOranges++;
14                }
15            }
16        }
17      
18        int minutesElapsed = 0; // Time counter for rotting process
19        int[] directions = {1, 0, -1, 0, 1}; // Directions for adjacent cells: right, down, left, up
20      
21        // Start BFS from initially rotten oranges
22        while (!queue.isEmpty() && freshOranges > 0) {
23            minutesElapsed++; // Increase time since each level of BFS represents 1 minute
24            for (int i = queue.size(); i > 0; --i) { // Iterate over rotten oranges at current time
25                int[] position = queue.poll();
26                for (int j = 0; j < 4; ++j) { // Check all adjacent cells
27                    int x = position[0] + directions[j]; 
28                    int y = position[1] + directions[j + 1];
29                    // If adjacent cell is within bounds and has a fresh orange
30                    if (x >= 0 && x < rows && y >= 0 && y < cols && grid[x][y] == 1) {
31                        grid[x][y] = 2; // Rot the fresh orange
32                        freshOranges--; // Decrement the fresh orange count
33                        queue.offer(new int[] {x, y}); // Enqueue the new rotten orange's position
34                    }
35                }
36            }
37        }
38      
39        // If there are still fresh oranges left, return -1, otherwise return elapsed time
40        return freshOranges > 0 ? -1 : minutesElapsed;
41    }
42}
43
1#include <vector>
2#include <queue>
3using namespace std;
4
5class Solution {
6public:
7    // Function to calculate the number of minutes until no fresh orange left.
8    int orangesRotting(vector<vector<int>>& grid) {
9        int rows = grid.size();          // Number of rows in the grid
10        int cols = grid[0].size();       // Number of columns in the grid
11        int freshCount = 0;              // Counter for fresh oranges
12        queue<pair<int, int>> rottenQueue; // Queue to maintain positions of rotten oranges
13      
14        // Initialize the queue with all rotten oranges and count fresh ones.
15        for (int i = 0; i < rows; ++i) {
16            for (int j = 0; j < cols; ++j) {
17                if (grid[i][j] == 2) {
18                    rottenQueue.emplace(i, j);
19                } else if (grid[i][j] == 1) {
20                    ++freshCount;
21                }
22            }
23        }
24      
25        // Time in minutes for rotting process.
26        int minutesElapsed = 0;
27        // Directions array that represents the 4 adjacent positions (up, right, down, left).
28        vector<int> directions = {-1, 0, 1, 0, -1};
29      
30        // Processing the grid until the queue is empty or all fresh oranges are rotten.
31        while (!rottenQueue.empty() && freshCount > 0) {
32            ++minutesElapsed; // Increase time since we're moving to next minute
33          
34            // Process all rotten oranges at the current time.
35            for (int i = rottenQueue.size(); i > 0; --i) {
36                // Fetch the coordinates of the current rotten orange.
37                auto position = rottenQueue.front();
38                rottenQueue.pop();
39                // Traverse 4 directions from the current rotten orange.
40                for (int j = 0; j < 4; ++j) {
41                    int newRow = position.first + directions[j];
42                    int newCol = position.second + directions[j + 1];
43                    // Check boundary conditions and whether the position contains a fresh orange.
44                    if (newRow >= 0 && newRow < rows && newCol >= 0 && newCol < cols && grid[newRow][newCol] == 1) {
45                        --freshCount;               // Fresh orange becomes rotten
46                        grid[newRow][newCol] = 2;  // Update grid to reflect rotten orange
47                        rottenQueue.emplace(newRow, newCol); // Add the new rotten orange to the queue
48                    }
49                }
50            }
51        }
52      
53        // Check if there are any fresh oranges left.
54        if (freshCount > 0) {
55            return -1; // Not all oranges can be rotten
56        } else {
57            return minutesElapsed; // All oranges are rotten, return total time taken
58        }
59    }
60};
61
1function orangesRotting(grid: number[][]): number {
2    const rows = grid.length;
3    const cols = grid[0].length;
4
5    let freshOranges = 0; // Counter for fresh oranges
6    const queue: [number, number][] = []; // Queue to store positions of rotten oranges
7
8    // Populate the queue with the initial positions of rotten oranges and count fresh oranges
9    for (let i = 0; i < rows; i++) {
10        for (let j = 0; j < cols; j++) {
11            if (grid[i][j] === 1) {
12                freshOranges++;
13            } else if (grid[i][j] === 2) {
14                queue.push([i, j]);
15            }
16        }
17    }
18
19    let minutes = 0; // Counter for elapsed minutes
20    // Directions for the adjacent cells (up, right, down, left)
21    const directions = [1, 0, -1, 0, 1]; 
22
23    // Loop until there are no more fresh oranges or the queue is empty
24    while (freshOranges !== 0 && queue.length !== 0) {
25        const currentLevelSize = queue.length; // Number of rotten oranges at the current minute
26
27        // Convert adjacent fresh oranges to rotten for each rotten orange in the queue
28        for (let i = 0; i < currentLevelSize; i++) {
29            const [x, y] = queue.shift(); // Get the next rotten orange position
30
31            // Check all four directions around the rotten orange
32            for (let j = 0; j < 4; j++) {
33                const newX = x + directions[j];
34                const newY = y + directions[j + 1];
35
36                // If the adjacent cell has a fresh orange, convert it to rotten
37                if (newX >= 0 && newX < rows && newY >= 0 && newY < cols && grid[newX][newY] === 1) {
38                    grid[newX][newY] = 2;
39                    queue.push([newX, newY]); // Add the new rotten orange position to the queue
40                    freshOranges--; // Decrease the count of fresh oranges
41                }
42            }
43        }
44
45        minutes++; // Increment the minutes after each level of adjacency check
46    }
47
48    // If there are any remaining fresh oranges, return -1, otherwise return the elapsed minutes
49    return freshOranges !== 0 ? -1 : minutes;
50}
51

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.


Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:
Question 1 out of 10

Consider the classic dynamic programming of longest increasing subsequence:

Find the length of the longest subsequence of a given sequence such that all elements of the subsequence are sorted in increasing order.

For example, the length of LIS for [50, 3, 10, 7, 40, 80] is 4 and LIS is [3, 7, 40, 80].

What is the recurrence relation?


Recommended Readings

Got a question? Ask the Monster Assistant anything you don't understand.

Still not clear?  Submit the part you don't understand to our editors. Or join our Discord and ask the community.

Cedric Chen

I don't think the posted solution is correct if we take the queue's size into consideration. Queue.size() will be dynamic and will prone to error. We need to store the size to be static.

1class Solution {
2    public int orangesRotting(int[][] grid) {
3        int rows = grid.length, cols = grid[0].length;
4        int freshOranges = 0;
5        Deque<int[]> queue = new LinkedList<>();
6
7        for (int i = 0; i< rows;i++) {
8            for (int j = 0; j < cols;j++) {
9                if (grid[i][j] == 2) {
10                    queue.offer(new int[]{i, j});
11                } else if (grid[i][j] == 1) {
12                    freshOranges++;
13                }
14            }
15        }
16
17        int minutesElapsed = 0;
18        int[][] directions = new int[][] {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
19
20        while (!queue.isEmpty() && freshOranges > 0) {
21            minutesElapsed++;
22            int currentQueueSize = queue.size();
23            for (int i = 0; i < currentQueueSize; i++) {
24                int[] position = queue.poll();
25                for (int j = 0; j < 4;j++) {
26                    int x = position[0] + directions[j][0];
27                    int y = position[1] + directions[j][1];
28                    if (x >= 0 && x < rows && y >= 0 && y < cols && grid[x][y] == 1) {
29                        grid[x][y] = 2;
30                        freshOranges--;
31                        queue.offer(new int[]{x, y});
32                    }
33
34                }
35            }
36        }
37
38        return freshOranges > 0? -1 : minutesElapsed;
39
40
41    }
42}
Tue Jul 30 2024