Rotting Oranges: Minimum Time to Rot All Oranges

57.4k
0

Given an R×C grid where 0 represents an empty cell, 1 represents a fresh orange, and 2 represents a rotten orange, return the minimum minutes required until no fresh orange remains.

Every minute, a rotten orange spreads rot to fresh oranges in four directions: up, down, left, and right. Return -1 when at least one fresh orange cannot become rotten.

Example 1

Input: grid = [[2,1,1],[1,1,0],[0,1,1]]

Output: 4

Explanation: Rot spreads level by level and reaches every fresh orange after four minutes.

Example 2

Input: grid = [[2,1,1],[0,1,1],[1,0,1]]

Output: -1

Explanation: The bottom-left fresh orange never touches any rotting chain through four-direction movement.

Brute Force Approach

Minute-by-minute simulation repeatedly scans the complete grid. During each minute, every rotten orange marks adjacent fresh oranges with a temporary value, preventing newly affected oranges from spreading before the next minute.

After a complete scan, temporary oranges become rotten and the minute counter increases. Repeated grid scans accurately simulate simultaneous spreading but produce a high time complexity.

Algorithm

  • Count all fresh oranges and initialize minutes to 0, allowing the simulation to stop after every fresh orange becomes rotten.

  • Continue the simulation while fresh oranges remain and initialize newlyRotten to 0 for the current minute.

  • Scan the grid using nested loops and mark every fresh neighbor of a rotten orange with a temporary value, preventing same-minute spreading while counting each newly affected orange once.

  • Return -1 when newlyRotten remains 0, as the remaining fresh oranges cannot be reached.

  • Scan the grid again to convert all temporary cells into rotten oranges and reduce the fresh-orange count accordingly.

  • Increment minutes after completing a successful spread round, since one full round represents one elapsed minute.

  • Return minutes after no fresh orange remains.

Dry Run

rotten orranges 1

rotten orranges 1

Solution

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
// Function to find minimum minutes using grid simulation.
int orangesRotting(vector<vector<int>>& grid) {
int rows = grid.size();
int cols = grid[0].size();
int fresh = 0;
int minutes = 0;
// Count all fresh oranges before simulation starts.
for (int row = 0; row < rows; row++) {
for (int col = 0; col < cols; col++) {
if (grid[row][col] == 1) {
fresh++;
}
}
}
vector<int> dRow = {-1, 1, 0, 0};
vector<int> dCol = {0, 0, -1, 1};
// Repeat minute-by-minute until no fresh orange remains.
while (fresh > 0) {
bool changed = false;
// Mark oranges becoming rotten during current minute.
for (int row = 0; row < rows; row++) {
for (int col = 0; col < cols; col++) {
if (grid[row][col] != 2) {
continue;
}
// Check four neighboring cells.
for (int dir = 0; dir < 4; dir++) {
int nextRow = row + dRow[dir];
int nextCol = col + dCol[dir];
if (nextRow >= 0 && nextCol >= 0 && nextRow < rows && nextCol < cols && grid[nextRow][nextCol] == 1) {
grid[nextRow][nextCol] = 3;
fresh--;
changed = true;
}
}
}
}
// No new orange rotted, so remaining fresh oranges are unreachable.
if (!changed) {
return -1;
}
// Commit all oranges marked for next minute.
for (int row = 0; row < rows; row++) {
for (int col = 0; col < cols; col++) {
if (grid[row][col] == 3) {
grid[row][col] = 2;
}
}
}
minutes++;
}
// Return total elapsed minutes.
return minutes;
}
};
// Driver code.
int main() {
vector<vector<int>> grid = {{2,1,1},{1,1,0},{0,1,1}};
Solution sol;
cout << sol.orangesRotting(grid);
return 0;
}

Complexity Analysis

Time Complexity: O((R×C)²), where R and C are the grid dimensions; up to R×C minutes can each require a complete grid scan.

Space Complexity: O(1), as only counters and a constant-sized direction array are used apart from the input grid.

Optimal Approach

Multi-source Breadth First Search begins from all initially rotten oranges simultaneously. Every BFS level contains oranges capable of spreading rot during the same minute.

Fresh oranges are marked rotten before queue insertion, ensuring that each orange enters the queue only once. Level-by-level processing eliminates repeated full-grid scans.

Algorithm

  • Scan the grid, add every initially rotten orange to a queue, and count all fresh oranges, creating the initial multi-source BFS frontier.

  • Return 0 when no fresh orange exists, as no spreading time is required.

  • Initialize minutes to 0 and continue BFS while the queue contains cells and fresh oranges remain.

  • Store the current queue size and process exactly that many oranges, ensuring that one BFS level represents one minute.

  • For every removed orange, inspect the four neighboring cells and convert each fresh neighbor to rotten before queue insertion, preventing duplicate processing.

  • Decrease freshCount for every newly rotten orange and increment minutes after the complete BFS level has been processed.

  • Return minutes when freshCount becomes 0; otherwise, return -1 because some fresh oranges are unreachable.

Dry Run

Diagram 1
1 / 2

Diagram 1

Solution

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
// Function to find minimum minutes using multi-source BFS.
int orangesRotting(vector<vector<int>>& grid) {
int rows = grid.size();
int cols = grid[0].size();
int fresh = 0;
int minutes = 0;
queue<pair<int, int>> q;
// Collect all rotten oranges as BFS sources.
for (int row = 0; row < rows; row++) {
for (int col = 0; col < cols; col++) {
if (grid[row][col] == 2) {
q.push({row, col});
} else if (grid[row][col] == 1) {
fresh++;
}
}
}
vector<int> dRow = {-1, 1, 0, 0};
vector<int> dCol = {0, 0, -1, 1};
// Process BFS level by level while fresh oranges remain.
while (!q.empty() && fresh > 0) {
int levelSize = q.size();
// Process all oranges rotting during current minute.
for (int count = 0; count < levelSize; count++) {
auto [row, col] = q.front();
q.pop();
// Spread rot to adjacent fresh oranges.
for (int dir = 0; dir < 4; dir++) {
int nextRow = row + dRow[dir];
int nextCol = col + dCol[dir];
if (nextRow >= 0 && nextCol >= 0 && nextRow < rows && nextCol < cols && grid[nextRow][nextCol] == 1) {
grid[nextRow][nextCol] = 2;
fresh--;
q.push({nextRow, nextCol});
}
}
}
minutes++;
}
// Return -1 when unreachable fresh oranges remain.
if (fresh > 0) {
return -1;
}
// Return minimum elapsed minutes.
return minutes;
}
};
// Driver code.
int main() {
vector<vector<int>> grid = {{2,1,1},{1,1,0},{0,1,1}};
Solution sol;
cout << sol.orangesRotting(grid);
return 0;
}

Complexity Analysis

Time Complexity: O(R×C), where R and C are the grid dimensions; every cell is scanned once and every orange enters the queue at most once.

Space Complexity: O(R×C), where the queue can store up to R×C orange coordinates in the worst case.

Interview follow-up Questions

BFS processes cells level by level, and each level naturally represents one minute of rot spread.

Graph

Read Similar Blogs

Graph

Disjoint Set Union: Union by Rank, Size and Path Compression

Input: N = 5 , operations = [unionByRank(1,2), unionByRank(2,3), find(1,3), find(1,5)] Output: [true, false] Explanation: Rank-based merges place nodes 1 , 2 , and 3 in one set. Node 5 remains in a...

89.1k
Graph

Print Shortest Path

Input: n = 5, m = 6, edges = [[1,2,2],[2,5,5],[2,3,4],[1,4,1],[4,3,3],[3,5,1]] Output: [5,1,4,3,5] Explanation: Path 1->4->3->5 has total weight 1+3+1=5 , which is minimum. Input: n = 2, m = 0, edg...

96.1k
Graph

Network Delay Time Using Dijkstra's Algorithm

A network contains n nodes labeled from 1 to n . Each directed edge [u,v,w] means a signal needs w time units to travel from node u to node v . A signal starts from node k . Return the minimum time...

81.2k
Comments0