Rotting Oranges - DSA Graphs
problem link: Rotting Oranges
Problem Statement
You are given an 𝑛 × 𝑚 grid where each cell can have one of three values:
- 0 → An empty cell
- 1 → A fresh orange
- 2 → A rotten orange
A rotten orange can rot adjacent fresh oranges (4-directionally: up, down, left, right) in one minute. Your task is to determine the minimum time required to rot all fresh oranges. If it's impossible to rot all oranges, return -1.
What Does 4-Directional Neighbor Mean?
Each orange in the grid has four possible neighbors:
- Up: (row - 1, same column)
- Down: (row + 1, same column)
- Left: (same row, column - 1)
- Right: (same row, column + 1)
If a fresh orange is present in any of these positions next to a rotten orange, it will rot in the next minute.
Understanding the Problem with Examples
Example 1
Input:
[[2,1,1],
[1,1,0],
[0,1,1]]
Step-by-step rotting process:
- Initially, the rotten orange at (0,0) can rot its adjacent fresh oranges.
[[2,2,1], [2,1,0], [0,1,1]]Time = 1 minute - Next minute, the newly rotten oranges at (0,1) and (1,0) spread rotting further:
[[2,2,2], [2,2,0], [0,1,1]]Time = 2 minutes - Third minute, the remaining fresh oranges rot:
[[2,2,2], [2,2,0], [0,2,1]]Time = 3 minutes - Final state:
[[2,2,2], [2,2,0], [0,2,2]]Time = 4 minutes
Output:
4
Example 2
Input:
[[2,1,1],
[0,1,1],
[1,0,1]]
Step-by-step rotting process:
- Initially, the rotten orange at (0,0) starts spreading
[[2,2,1], [0,1,1], [1,0,1]]Time = 1 minute - Next minute, the newly rotten orange at (0,1) spreads to (0,2):
[[2,2,2], [0,2,1], [1,0,1]]Time = 2 minutes - Next minute:
[[2,2,2], [0,2,2], [1,0,1]]Time = 3 minutes - Next minute:
[[2,2,2], [0,2,2], [1,0,2]]Time = 4 minutes - At this point, the rotting process stops!
- The fresh oranges at (2,0) is completely isolated because there is no path from any rotten orange to it.
- Since this fresh orange cannot be reached, it will never rot.
Final State:
[[2,2,2],
[0,2,2],
[1,0,2]]
Since some fresh oranges remain unrotted, we return -1.
Output:
-1
Key Observations
Queue Initialization
We start by identifying all the rotten oranges and storing their positions in a queue.
This helps us process all rotten oranges at the same time (layer by layer), ensuring that the rotting spreads efficiently.
Layer-by-Layer Processing in BFS
When we say "layer-by-layer", we mean that at each minute, we process all the rotten oranges present in the queue simultaneously before moving to the next batch of newly rotten oranges.
In a single BFS step (one minute),:
- We remove all currently rotten oranges from the queue.
- For each rotten orange, we check its 4-directional neighbors (up, down, left, right).
- If a fresh orange is found in any of these positions, it rots and is added to the queue for processing in the next minute.
This ensures that the rotting process happens in waves, affecting all fresh oranges adjacent to rotten ones at the same time.
Count Fresh Oranges
Count the total number of fresh oranges in the grid. This helps determine when all fresh oranges have rotted and when to stop the process.
Perform BFS Traversal
We process each rotten orange from the queue, checking its 4-directional neighbors.
If a neighboring cell contains a fresh orange, it will rot and be added to the queue for the next round.
Track Time in Minutes
Each BFS iteration represents one minute. We keep track of how many minutes it takes for all reachable fresh oranges to rot.
Edge Case - Isolated Fresh Oranges
If, after BFS, there are still fresh oranges left (i.e., they could not be reached by any rotten orange), return -1.
Code Implementations
Below are the implementations in Java and C++.
JAVA
import java.util.LinkedList;
import java.util.Queue;
class Solution {
public int orangesRotting(int[][] grid) {
int rows = grid.length;
int cols = grid[0].length;
Queue queue = new LinkedList<>();
int freshOranges = 0;
// Step 1: Add all initially rotten oranges to the queue
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
if (grid[i][j] == 2) {
queue.add(new int[]{i, j});
} else if (grid[i][j] == 1) {
freshOranges++;
}
}
}
if (freshOranges == 0) return 0; // No fresh oranges to rot
int minutes = 0;
int[][] directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}}; // 4-directional movement
// Step 2: Perform BFS layer by layer
while (!queue.isEmpty()) {
int size = queue.size();
boolean rottedThisMinute = false;
for (int i = 0; i < size; i++) {
int[] rotten = queue.poll();
int r = rotten[0], c = rotten[1];
for (int[] dir : directions) {
int nr = r + dir[0], nc = c + dir[1];
if (nr >= 0 && nr < rows && nc >= 0 && nc < cols && grid[nr][nc] == 1) {
grid[nr][nc] = 2; // Rot the fresh orange
queue.add(new int[]{nr, nc});
freshOranges--;
rottedThisMinute = true;
}
}
}
// If there were no rotting this minute, it means some fresh oranges are unreachable
if (rottedThisMinute) {
minutes++;
}
}
return freshOranges == 0 ? minutes : -1;
}
}
Time and Space Complexity Analysis
Time Complexity: O(N × M)
- Each cell in the grid is processed at most once during the BFS traversal.
- We traverse through all the cells in the grid initially to count fresh oranges and add rotten ones to the queue (O(N × M)).
- The BFS traversal also visits each cell at most once, making the total complexity O(N × M).
Space Complexity: O(N × M)
- The worst-case scenario occurs when all oranges are fresh except one rotten orange.
- In such a case, the queue stores almost all the oranges at some point.
- Since we use an auxiliary queue for BFS, the space complexity remains O(N × M).
Conclusion
- We used BFS (Breadth-First Search) to spread the rotting process layer by layer efficiently.
- The problem was solved optimally in O(N × M) time, making it efficient for large grids.
- If any fresh orange remains unrotted, we return -1. Otherwise, we return the minimum time required for all oranges to rot.
- The key takeaway is that BFS is ideal for shortest-path problems in an unweighted grid, ensuring all elements in a layer are processed simultaneously.