Rotting Oranges
MedPrompt
You are given an m x n grid where each cell can have one of three values:
0representing an empty cell,1representing a fresh orange, or2representing 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.
Example 1:
Input: grid = [[2,1,1],[1,1,0],[0,1,1]]
Output: 4Example 2:
Input: grid = [[2,1,1],[0,1,1],[1,0,1]]
Output: -1
Explanation: The orange in the bottom left corner (row 2, column 0) is never rotten, because rotting only happens 4-directionally.Example 3:
Input: grid = [[0,2]]
Output: 0
Explanation: Since there are already no fresh oranges at minute 0, the answer is just 0.
Constraints:
m == grid.lengthn == grid[i].length1 <= m, n <= 10grid[i][j]is0,1, or2.
Approaches
2 approaches with complexity analysis and trade-offs.
This approach directly simulates the rotting process minute by minute. In each time step, it performs a full scan of the grid to identify all fresh oranges that are adjacent to a rotten one. These oranges are then marked to become rotten in the next minute. The simulation continues until no more oranges can rot. Finally, it checks if any fresh oranges remain to determine if the task was possible.
Algorithm
- Initialize
minutes = 0and count the total number offreshOranges. - If
freshOrangesis 0, the process is already complete, so return 0. - Enter a loop that continues as long as there are fresh oranges remaining.
- In each iteration (representing one minute), create a temporary list,
toRot, to store the coordinates of fresh oranges that will become rotten in this minute. - Iterate through every cell
(r, c)of the grid. - If a cell contains a fresh orange (
grid[r][c] == 1), check its four neighbors. - If any neighbor is a rotten orange (
grid[r][c] == 2), add the coordinates(r, c)to thetoRotlist and stop checking neighbors for this cell. - After scanning the entire grid, if the
toRotlist is empty, it means no more oranges can rot, but fresh ones still exist. This indicates an impossible scenario, so we break the loop. - For each orange in the
toRotlist, update its state in the grid to rotten (2) and decrement thefreshOrangescount. - Increment the
minutescounter. - After the loop terminates, if
freshOrangesis 0, returnminutes. Otherwise, return -1.
Walkthrough
The brute-force method involves simulating the process in discrete time steps. We start by counting the initial number of fresh oranges. Then, we enter a loop that models the passing of time. In each iteration, which corresponds to one minute, we scan the entire grid. We use a temporary list to collect the coordinates of all fresh oranges that are adjacent to any rotten orange from the beginning of that minute. It's crucial to use a temporary list to ensure that an orange that turns rotten in the current minute doesn't cause another fresh orange to rot in the same minute, as rotting happens simultaneously. After the scan, we update the state of all oranges in the temporary list to rotten. We increment our minute counter and repeat the process. If a full pass occurs where no new oranges rot but fresh ones still exist, we know some are unreachable, and the task is impossible. The simulation ends when there are no more fresh oranges left.
class Solution { public int orangesRotting(int[][] grid) { int freshCount = 0; int rows = grid.length; int cols = grid[0].length; for (int r = 0; r < rows; r++) { for (int c = 0; c < cols; c++) { if (grid[r][c] == 1) { freshCount++; } } } if (freshCount == 0) { return 0; } int minutes = 0; int[] dr = {-1, 1, 0, 0}; int[] dc = {0, 0, -1, 1}; while (freshCount > 0) { java.util.List<int[]> toRot = new java.util.ArrayList<>(); for (int r = 0; r < rows; r++) { for (int c = 0; c < cols; c++) { if (grid[r][c] == 1) { for (int i = 0; i < 4; i++) { int nr = r + dr[i]; int nc = c + dc[i]; if (nr >= 0 && nr < rows && nc >= 0 && nc < cols && grid[nr][nc] == 2) { toRot.add(new int[]{r, c}); break; // Found a rotten neighbor, move to the next fresh orange } } } } } if (toRot.isEmpty()) { return -1; // No oranges rotted, but fresh ones remain. } for (int[] orange : toRot) { // Use a temporary state to avoid chain reactions in the same minute. // An orange that becomes rotten now should only affect others in the *next* minute. // We mark with 3 first to distinguish from oranges rotten at the start of the minute. grid[orange[0]][orange[1]] = 3; } // Now, finalize the state for the next minute's simulation. for (int[] orange : toRot) { grid[orange[0]][orange[1]] = 2; } freshCount -= toRot.size(); minutes++; } return minutes; }}Complexity
Time
O((M * N)^2). In each minute of the simulation, we scan the entire grid, which takes O(M * N) time. The number of minutes could be up to M * N in the worst case (e.g., a long snake-like path of oranges). This results in a quadratic time complexity.
Space
O(M * N), where M and N are the dimensions of the grid. In the worst case, the `toRot` list could store coordinates for nearly all the cells.
Trade-offs
Pros
Conceptually simple and easy to follow as it directly models the real-world process.
Cons
Highly inefficient due to repeated O(M*N) scans of the grid in each minute.
The time complexity of O((M*N)^2) makes it too slow for larger grids.
This problem can be modeled as finding the shortest path in an unweighted graph, which is a perfect use case for Breadth-First Search (BFS). We can treat this as a multi-source BFS problem, where all initially rotten oranges are the sources. The BFS explores the grid layer by layer, where each layer corresponds to one minute of time passing. This efficiently calculates the minimum time for all fresh oranges to become rotten.
Algorithm
- Initialize a queue and add the coordinates of all initially rotten oranges (value 2).
- Scan the grid to count the total number of
freshOranges(value 1). - If
freshOrangesis 0, return 0. - Initialize
minutes = 0. - Start a
whileloop that runs as long as the queue is not empty and there are still fresh oranges. - Inside the loop, increment
minutesas we are processing a new level of rotting. - Get the current
levelSizeof the queue. This represents all oranges that became rotten in the previous minute. - Loop
levelSizetimes:- Dequeue a rotten orange's coordinates
(r, c). - For each of its 4-directional neighbors
(nr, nc): - Check if the neighbor is within grid boundaries and is a fresh orange (
grid[nr][nc] == 1). - If it is, update the grid
grid[nr][nc] = 2, decrementfreshOranges, and enqueue the new rotten orange's coordinates(nr, nc).
- Dequeue a rotten orange's coordinates
- After the main
whileloop finishes, check iffreshOrangesis 0. If it is, all oranges have rotted, so returnminutes. Otherwise, some were unreachable, so return -1.
Walkthrough
The optimal approach treats the grid as a graph and uses a multi-source Breadth-First Search (BFS). The sources of the BFS are all cells that initially contain a rotten orange.
First, we iterate through the grid once to identify all initial rotten oranges, adding their coordinates to a queue. During this scan, we also count the total number of fresh oranges. This initial count is crucial for the final check.
Then, the BFS begins. It proceeds in levels. Each level of the BFS corresponds to one minute of the rotting process. We use a loop that continues as long as there are rotten oranges in our queue to spread from. In each iteration of this main loop, we process all oranges currently in the queue (a single level). For each rotten orange we dequeue, we check its four neighbors. If a neighbor is a fresh orange, we change its state to rotten, add its coordinates to the queue for the next level, and decrement our freshOranges counter.
After the BFS completes (the queue is empty), we check if the freshOranges counter has reached zero. If it has, it means every fresh orange was reached and rotted, and we return the total minutes elapsed. If the counter is still greater than zero, it means some fresh oranges were isolated and could not be reached, so we return -1.
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; int cols = grid[0].length; Queue<int[]> queue = new LinkedList<>(); int freshCount = 0; // Find initial rotten oranges and count fresh oranges for (int r = 0; r < rows; r++) { for (int c = 0; c < cols; c++) { if (grid[r][c] == 2) { queue.offer(new int[]{r, c}); } else if (grid[r][c] == 1) { freshCount++; } } } if (freshCount == 0) { return 0; } int minutes = 0; int[][] directions = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}}; // Start BFS from all initial rotten oranges while (!queue.isEmpty() && freshCount > 0) { minutes++; int levelSize = queue.size(); for (int i = 0; i < levelSize; i++) { int[] point = queue.poll(); for (int[] dir : directions) { int r = point[0] + dir[0]; int c = point[1] + dir[1]; if (r < 0 || r >= rows || c < 0 || c >= cols || grid[r][c] != 1) { continue; } grid[r][c] = 2; queue.offer(new int[]{r, c}); freshCount--; } } } return freshCount == 0 ? minutes : -1; }}Complexity
Time
O(M * N). We perform an initial scan of the grid, which takes O(M * N). The subsequent BFS ensures that each cell is enqueued and dequeued at most once. Thus, the overall time complexity is linear with respect to the number of cells in the grid.
Space
O(M * N). In the worst-case scenario, the queue could hold all the cells in the grid (e.g., a checkerboard pattern of fresh and rotten oranges).
Trade-offs
Pros
Optimal time complexity of O(M*N).
Efficiently handles the simultaneous rotting from multiple sources.
Guaranteed to find the minimum time if a solution exists.
Cons
Requires extra space for the queue, which can be up to O(M*N) in the worst case.
Solutions
Solution
class Solution {public int orangesRotting(int[][] grid) { int m = grid.length, n = grid[0].length; int cnt = 0; Deque<int[]> q = new LinkedList<>(); for (int i = 0; i < m; ++i) { for (int j = 0; j < n; ++j) { if (grid[i][j] == 2) { q.offer(new int[]{i, j}); } else if (grid[i][j] == 1) { ++cnt; } } } int ans = 0; int[] dirs = {1, 0, -1, 0, 1}; while (!q.isEmpty() && cnt > 0) { ++ans; for (int i = q.size(); i > 0; --i) { int[] p = q.poll(); for (int j = 0; j < 4; ++j) { int x = p[0] + dirs[j]; int y = p[1] + dirs[j + 1]; if (x >= 0 && x < m && y >= 0 && y < n && grid[x][y] == 1) { grid[x][y] = 2; --cnt; q.offer(new int[]{x, y}); } } } } return cnt > 0 ? -1 : ans; }}/** * @param {number[][]} grid * @return {number} */ var orangesRotting = function ( grid ) { const m = grid . length ; const n = grid [ 0 ]. length ; let q = []; let cnt = 0 ; for ( let i = 0 ; i < m ; ++ i ) { for ( let j = 0 ; j < n ; ++ j ) { if ( grid [ i ][ j ] === 1 ) { cnt ++ ; } else if ( grid [ i ][ j ] === 2 ) { q . push ([ i , j ]); } } } const dirs = [ - 1 , 0 , 1 , 0 , - 1 ]; for ( let ans = 1 ; q . length && cnt ; ++ ans ) { let t = []; for ( const [ i , j ] of q ) { for ( let d = 0 ; d < 4 ; ++ d ) { const x = i + dirs [ d ]; const y = j + dirs [ d + 1 ]; if ( x >= 0 && x < m && y >= 0 && y < n && grid [ x ][ y ] === 1 ) { grid [ x ][ y ] = 2 ; t . push ([ x , y ]); if ( -- cnt === 0 ) { return ans ; } } } } q = [... t ]; } return cnt > 0 ? - 1 : 0 ; };class Solution {public: int orangesRotting(vector<vector<int>> &grid) { int m = grid.size(), n = grid[0].size(); int cnt = 0; typedef pair<int, int> pii; queue<pii> q; for (int i = 0; i < m; ++i) { for (int j = 0; j < n; ++j) { if (grid[i][j] == 2) q.emplace(i, j); else if (grid[i][j] == 1) ++cnt; } } int ans = 0; vector<int> dirs = {-1, 0, 1, 0, -1}; while (!q.empty() && cnt > 0) { ++ans; for (int i = q.size(); i > 0; --i) { auto p = q.front(); q.pop(); for (int j = 0; j < 4; ++j) { int x = p.first + dirs[j]; int y = p.second + dirs[j + 1]; if (x >= 0 && x < m && y >= 0 && y < n && grid[x][y] == 1) { --cnt; grid[x][y] = 2; q.emplace(x, y); } } } } return cnt > 0 ? -1 : ans; }};class Solution: def orangesRotting(self, grid: List[List[int]]) -> int: m, n = len(grid), len(grid[0]) q = deque() cnt = 0 for i in range(m): for j in range(n): if grid[i][j] == 2: q . append((i, j)) elif grid[i][j] == 1: cnt += 1 ans = 0 while q and cnt: ans += 1 for _ in range(len(q)): i, j = q . popleft() for a, b in [[0, 1], [0, - 1], [1, 0], [- 1, 0]]: x, y = i + a, j + b if 0 <= x < m and 0 <= y < n and grid[x][y] == 1: cnt -= 1 grid[x][y] = 2 q . append((x, y)) return ans if cnt == 0 else - 1Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.