Rotting Oranges
Problem link: https://leetcode.com/problems/rotting-oranges/
Problem Statement
You are given an m x n grid where each cell can have one of three values: 0 → empty cell 1 → fresh orange 2 → rotten orange
Every minute, any fresh orange adjacent (4-directionally) to a rotten orange becomes rotten.
Return the minimum number of minutes required to rot all oranges. If impossible, return -1.
Input
A 2D grid of size m x n containing values 0, 1, or 2.
Output
Return minimum minutes required to rot all oranges, or -1 if not possible.
Example
Input: grid = [[2,1,1],[1,1,0],[0,1,1]]
Output: 4
Explanation
All rotten oranges spread simultaneously. Each BFS level represents 1 minute.
Minute 0: Initial rotten oranges Minute 1+: Spread to adjacent fresh oranges
Final answer = total BFS levels required
Brute Force
Intuition
Simulate minute by minute. For each minute, scan the entire grid and convert fresh oranges adjacent to rotten ones. Repeat until no changes occur.
Approach
- Loop until no changes occur
- Traverse full grid
- For each rotten orange, mark adjacent fresh oranges
- Apply updates
- Count minutes
Dry Run
Each iteration processes entire grid → inefficient. Time increases even if few oranges are changing.
Code (Java)
class Solution {
public int orangesRotting(int[][] grid) {
int m = grid.length, n = grid[0].length;
int minutes = 0;
boolean changed;
do {
changed = false;
int[][] copy = new int[m][n];
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
copy[i][j] = grid[i][j];
}
}
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (grid[i][j] == 2) {
int[][] dir = {{1,0},{-1,0},{0,1},{0,-1}};
for (int[] d : dir) {
int ni = i + d[0], nj = j + d[1];
if (ni>=0 && nj>=0 && ni<m && nj<n && grid[ni][nj] == 1) {
copy[ni][nj] = 2;
changed = true;
}
}
}
}
}
if (changed) minutes++;
grid = copy;
} while (changed);
for (int[] row : grid) {
for (int cell : row) {
if (cell == 1) return -1;
}
}
return minutes;
}
}
Complexity Analysis
Each iteration scans full grid, and worst-case we do this O(m*n) times.
Optimal Solution
Intuition
All rotten oranges act as starting points. Spread happens simultaneously → BFS level order traversal.
Approach
- Add all rotten oranges to queue
- Count fresh oranges
- Perform BFS
- For each level:
- Rot adjacent fresh oranges
- Decrease fresh count
- Increment time per level
- If fresh remains → return -1
Dry Run
Queue initially has all rotten oranges. Each BFS level spreads rot. Time increments after each level.
Code (Java)
Complexity Analysis
Each cell is processed once in BFS.
Quick Revision (Brute Force)
- Simulate minute-by-minute
- Scan full grid repeatedly
- High time complexity
Quick Revision (Optimal)
- Multi-source BFS
- Each level = 1 minute
- Process all rotten together