Stacks & QueuesProblem 31 of 38
Minimum time required to rot all oranges
Problem Statement
Given a grid of size m x n where each cell can have one of three values:
0: Empty cell1: Fresh orange2: Rotten orange
Every minute, any fresh orange that is 4-directionally adjacent to a rotten orange becomes rotten. Return the minimum number of minutes until no fresh orange remains. If this is impossible, return -1.
Example:
Input: grid = [[2,1,1],
[1,1,0],
[0,1,1]]
Output: 4
Minute 0: Initial state
[[2,1,1],
[1,1,0],
[0,1,1]]
Minute 1: Adjacent to initial rotten
[[2,2,1],
[2,1,0],
[0,1,1]]
Minute 2:
[[2,2,2],
[2,2,0],
[0,1,1]]
Minute 3:
[[2,2,2],
[2,2,0],
[0,2,1]]
Minute 4: All rotted
[[2,2,2],
[2,2,0],
[0,2,2]]
Approach 1: Brute Force (Simulation)
Intuition
Simulate the process minute by minute. In each minute, find all fresh oranges adjacent to rotten ones and mark them as rotten. Repeat until no more oranges can rot.
Algorithm
- Repeat until no change:
- For each cell, if it's a fresh orange adjacent to a rotten one, mark it for rotting
- Apply all the markings
- Increment time
- Check if any fresh oranges remain
java
import java.util.*;
public class RottingOranges {
public static int orangesRottingBruteForce(int[][] grid) {
int m = grid.length;
int n = grid[0].length;
int minutes = 0;
int[] dx = {-1, 1, 0, 0};
int[] dy = {0, 0, -1, 1};
while (true) {
List<int[]> toRot = new ArrayList<>();
// Find all fresh oranges adjacent to rotten ones
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (grid[i][j] == 1) {
for (int d = 0; d < 4; d++) {
int ni = i + dx[d];
int nj = j + dy[d];
if (ni >= 0 && ni < m && nj >= 0 && nj < n
&& grid[ni][nj] == 2) {
toRot.add(new int[]{i, j});
break;
}
}
}
}
}
if (toRot.isEmpty()) break;
for (int[] p : toRot) {
grid[p[0]][p[1]] = 2;
}
minutes++;
}
// Check if any fresh oranges remain
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (grid[i][j] == 1) return -1;
}
}
return minutes;
}
}Complexity Analysis
- Time Complexity: O((mn)^2) - potentially O(mn) minutes, each scanning entire grid
- Space Complexity: O(m*n) - storing cells to rot
Approach 2: Optimal (Multi-source BFS)
Intuition
Use BFS starting from all rotten oranges simultaneously. This is a multi-source BFS where all initial rotten oranges are at distance 0. Each level of BFS represents one minute.
Algorithm
- Add all initially rotten oranges to queue
- Count all fresh oranges
- BFS level by level:
- Process all current rotten oranges
- For each, rot adjacent fresh oranges
- Add newly rotten oranges to queue
- Increment time after each level
- If fresh count > 0, return -1
java
import java.util.*;
public class RottingOranges {
public static int orangesRotting(int[][] grid) {
int m = grid.length;
int n = grid[0].length;
Queue<int[]> queue = new LinkedList<>();
int freshCount = 0;
// Add all rotten oranges to queue, count fresh oranges
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (grid[i][j] == 2) {
queue.offer(new int[]{i, j});
} else if (grid[i][j] == 1) {
freshCount++;
}
}
}
// If no fresh oranges, return 0
if (freshCount == 0) return 0;
int minutes = 0;
int[] dx = {-1, 1, 0, 0};
int[] dy = {0, 0, -1, 1};
// BFS level by level
while (!queue.isEmpty()) {
int size = queue.size();
boolean rotted = false;
for (int i = 0; i < size; i++) {
int[] curr = queue.poll();
int x = curr[0], y = curr[1];
for (int d = 0; d < 4; d++) {
int nx = x + dx[d];
int ny = y + dy[d];
if (nx >= 0 && nx < m && ny >= 0 && ny < n
&& grid[nx][ny] == 1) {
grid[nx][ny] = 2;
queue.offer(new int[]{nx, ny});
freshCount--;
rotted = true;
}
}
}
if (rotted) minutes++;
}
return (freshCount == 0) ? minutes : -1;
}
public static void main(String[] args) {
int[][] grid1 = {{2,1,1}, {1,1,0}, {0,1,1}};
System.out.println("Test 1: " + orangesRotting(grid1)); // 4
int[][] grid2 = {{2,1,1}, {0,1,1}, {1,0,1}};
System.out.println("Test 2: " + orangesRotting(grid2)); // -1
int[][] grid3 = {{0,2}};
System.out.println("Test 3: " + orangesRotting(grid3)); // 0
}
}Complexity Analysis
- Time Complexity: O(m*n) - each cell visited at most once
- Space Complexity: O(m*n) - queue can hold all cells in worst case
Visual Walkthrough
Initial State (Minute 0):
[2, 1, 1] R = Rotten (2)
[1, 1, 0] F = Fresh (1)
[0, 1, 1] - = Empty (0)
Queue: [(0,0)]
Fresh Count: 6
Minute 1: Process (0,0), rot neighbors
[2, 2, 1]
[2, 1, 0]
[0, 1, 1]
Queue: [(0,1), (1,0)]
Fresh Count: 4
Minute 2: Process (0,1), (1,0)
[2, 2, 2]
[2, 2, 0]
[0, 1, 1]
Queue: [(0,2), (1,1)]
Fresh Count: 2
Minute 3: Process (0,2), (1,1)
[2, 2, 2]
[2, 2, 0]
[0, 2, 1]
Queue: [(2,1)]
Fresh Count: 1
Minute 4: Process (2,1)
[2, 2, 2]
[2, 2, 0]
[0, 2, 2]
Queue: [(2,2)]
Fresh Count: 0
Result: 4 minutes
Key Takeaways
- Multi-source BFS: Start BFS from all sources simultaneously
- Level Order: Each BFS level represents one time unit
- Fresh Count: Track fresh oranges to detect impossibility
- Edge Cases: No fresh oranges = 0, isolated fresh oranges = -1
- This is LeetCode #994 - Rotting Oranges
- Similar pattern applies to: fire spreading, disease spreading, flood fill