Rotten Orange (Using BFS)
DT
Problem Overview
In the "Rotting Oranges" problem (LeetCode #994), you're given a grid that represents a box of oranges. Each cell in the grid can have one of the following three states:
0representing an empty cell.1representing a fresh orange.2representing a rotten orange.
Every minute, any fresh orange that is adjacent (4-directionally) to a rotten orange becomes rotten. The task is to determine the minimum number of minutes that must elapse until no cell has a fresh orange. If it is impossible to rot all the oranges, return -1.
Understanding the Problem
The problem describes a scenario where oranges can rot over time via adjacent transmission. We need to simulate this process and compute the total time required for all fresh oranges to rot. If some fresh oranges are isolated from all rotten oranges, they will never rot, and the result should be -1.
This can be thought of as a multi-source breadth-first search (BFS) problem, where each rotten orange is an initial source.
Key DSA Concepts and Theory
Breadth-First Search (BFS)
BFS is an algorithm for traversing or searching tree or graph data structures. It explores all of the neighbor nodes at the present depth prior to moving on to nodes at the next depth level. BFS is useful for finding the shortest path on unweighted graphs, and it can be implemented using a queue.
Queue
A queue is a collection of entities that are maintained in a sequence and can be modified by the addition of entities at one end and the removal of entities from the other end. This makes it a first-in, first-out (FIFO) data structure.
In this problem, a queue is used to store the current layer of rotten oranges and propagate this to fresh ones level by level.
Solution Approach
Step-by-Step Solution
- Initialize a queue to store all currently rotten oranges since they are our starting points for BFS.
- Count all fresh oranges in the grid.
- Perform Multi-source BFS:
- Process each orange in the queue and, for each rotten orange, check its 4-directional neighbors.
- If a neighbor is a fresh orange (
1), turn it into a rotten orange (2) and add it to the queue. - Decrease the count of fresh oranges by one when a fresh orange becomes rotten.
- Keep a counter to track the number of layers (minutes) it takes.
- Check if all oranges are rotten:
- If there are no fresh oranges remaining, return the time counter.
- If there are fresh oranges left, return
-1.
C++ Code Example
#include <vector>
#include <queue>
using namespace std;
int orangesRotting(vector<vector<int>>& grid) {
int rows = grid.size();
int cols = grid[0].size();
queue<pair<int, int>> rottenQueue;
int freshCount = 0;
int minutes = 0;
// Add all initial rotten oranges to the queue and count fresh oranges
for (int r = 0; r < rows; ++r) {
for (int c = 0; c < cols; ++c) {
if (grid[r][c] == 2) {
rottenQueue.push({r, c});
} else if (grid[r][c] == 1) {
freshCount++;
}
}
}
// Directions for 4-directional adjacency
vector<pair<int, int>> directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
// BFS to rot adjacent fresh oranges
while (!rottenQueue.empty() && freshCount > 0) {
int size = rottenQueue.size(); // each minute process one layer
for (int i = 0; i < size; ++i) {
auto [r, c] = rottenQueue.front();
rottenQueue.pop();
for (auto [dr, dc] : directions) {
int newR = r + dr;
int newC = c + dc;
if (newR >= 0 && newR < rows && newC >= 0 && newC < cols && grid[newR][newC] == 1) {
grid[newR][newC] = 2;
freshCount--;
rottenQueue.push({newR, newC});
}
}
}
minutes++;
}
return freshCount == 0 ? minutes : -1;
}
Java Code Example
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<int[]> rottenQueue = new LinkedList<>();
int freshCount = 0;
int minutes = 0;
// Add all initial rotten oranges to the queue and count fresh oranges
for (int r = 0; r < rows; r++) {
for (int c = 0; c < cols; c++) {
if (grid[r][c] == 2) {
rottenQueue.add(new int[]{r, c});
} else if (grid[r][c] == 1) {
freshCount++;
}
}
}
// Directions for 4-directional adjacency
int[][] directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
// BFS to rot adjacent fresh oranges
while (!rottenQueue.isEmpty() && freshCount > 0) {
int size = rottenQueue.size(); // each minute process one layer
for (int i = 0; i < size; i++) {
int[] current = rottenQueue.poll();
int r = current[0];
int c = current[1];
for (int[] dir : directions) {
int newR = r + dir[0];
int newC = c + dir[1];
if (newR >= 0 && newR < rows && newC >= 0 && newC < cols && grid[newR][newC] == 1) {
grid[newR][newC] = 2;
freshCount--;
rottenQueue.add(new int[]{newR, newC});
}
}
}
minutes++;
}
return freshCount == 0 ? minutes : -1;
}
}
Time and Space Complexity Analysis
- Time Complexity: O(N), where N is the number of cells in the grid. Each cell is visited at most once, and all adjacent cells are processed in constant time.
- Space Complexity: O(N) to store freshly rotten oranges in the queue.
Common Mistakes to Avoid
- Not counting initial fresh oranges: Ensure to count all fresh oranges correctly. If BFS completes but fresh oranges remain, then return
-1. - Boundary checks: Always validate grid boundaries when processing adjacent cells.
Similar Problems on LeetCode
- LeetCode #286: Walls and Gates
- LeetCode #542: 01 Matrix