DSA
Rotten Oranges
Graphs. Time O(V^2).
You are given an m x n grid where each cell can have one of three values:
0 representing an empty cell, 1 representing a fresh orange, or 2 representing a rotten orange. Every minute, any fresh orange that is 4-directionally adjacent to a rotten orange becomes rotten.
Return the minimum number of minutes that must elapse until no cell has a fresh orange. If this is impossible, return -1.
Practice Link
Multi-Source BFS#
The spreading rot process is a textbook multi-source BFS: all initially rotten oranges infect their neighbours simultaneously each minute, which maps directly to processing one complete BFS level per minute. We seed the queue with every rotten orange at the start (multi-source), then count BFS levels — each level represents one minute of spreading. We also track the number of fresh oranges and decrement it as oranges turn rotten; after BFS completes, if any fresh oranges remain they are unreachable (isolated by empty cells) and we return -1. The time variable starts at -1 to compensate for the off-by-one: we increment it once per BFS level including the initial empty round, so the final value equals the actual number of minutes elapsed.
Sample#
Input: grid = [[2,1,1],[1,1,0],[0,1,1]]
Output: 4
Implementation#
class Solution {
public:
vector<int> dx = {0,0,1,-1};
vector<int> dy = {1,-1,0,0};
bool isValidCell(vector<vector<int>>& grid, int x, int y)
{
if(x<0 || x>=grid.size() || y<0 || y>= grid[0].size())
return false;
return true;
}
int orangesRotting(vector<vector<int>>& grid) {
int m = grid.size();
int n = grid[0].size();
int freshOranges = 0;
queue<pair<int,int>> rottenOranges;
for(int i=0;i<m;i++)
{
for(int j=0;j<n;j++)
{
if(grid[i][j]==2)
rottenOranges.push({i,j});
else if(grid[i][j]==1)
freshOranges++;
}
}
if(freshOranges==0)
return 0;
int time = -1;
while(!rottenOranges.empty())
{
int size = rottenOranges.size();
for(int i=0;i<size;i++)
{
int row = rottenOranges.front().first;
int col = rottenOranges.front().second;
rottenOranges.pop();
for(int dir=0;dir<4;dir++)
{
int newRow = row + dx[dir];
int newCol = col + dy[dir];
if(isValidCell(grid, newRow, newCol) && grid[newRow][newCol]==1)
{
grid[newRow][newCol] = 2;
rottenOranges.push({newRow, newCol});
freshOranges--;
}
}
}
time++;
}
if(freshOranges > 0)
return -1;
if(time==-1)
return 0;
return time;
}
};
Time Complexity: O(m × n) — every cell is enqueued and dequeued at most once.
Space Complexity: O(m × n) — the queue can hold all cells in the worst case.
Follow-up: Sparse Graph of Oranges#
The grid representation scans every cell during initialisation — O(m × n) — even if there are only a handful of oranges. When the grid is huge but sparse (very few oranges, lots of empty space), that initial scan dominates needlessly.
How the logic changes with a sparse graph:
Instead of a 2-D grid, model the input as an adjacency list where nodes are (row, col) positions of oranges only, and edges connect 4-directionally adjacent orange pairs.
Input: list of (row, col, state) triples — only cells that have an orange
Build: adjacency list { node → [neighbours that are fresh oranges] }
The BFS structure stays identical — multi-source from all rotten nodes — but:
| Aspect | Grid BFS | Sparse Graph BFS |
|---|---|---|
| Init scan | O(m × n) | O(F + R) — F fresh, R rotten |
| Neighbour lookup | O(1) via bounds check | O(degree) via adjacency list |
| Space | O(m × n) | O(F + R + edges) |
| Best for | Dense grids | m, n huge but few oranges |
// Sparse representation
unordered_map<string, vector<string>> adj; // node → fresh neighbours
queue<string> q; // seeded with rotten nodes
int fresh = 0;
auto key = [](int r, int c) { return to_string(r) + "," + to_string(c); };
for (auto& [r, c, state] : oranges) {
if (state == 2) q.push(key(r, c));
else fresh++;
// build adj by checking which neighbours exist in the orange set
}
int minutes = 0;
while (!q.empty() && fresh > 0) {
int sz = q.size();
while (sz--) {
auto node = q.front(); q.pop();
for (auto& nb : adj[node]) {
if (/* nb is still fresh */) {
// mark rotten, enqueue, fresh--
}
}
}
minutes++;
}
return fresh == 0 ? minutes : -1;
Key insight: the BFS wave-propagation logic is unchanged — only the data structure representing the graph differs. When oranges are sparse, skipping the full grid scan and working directly on the orange nodes reduces both time and memory from O(m × n) to O(F + R + E), where E is the number of adjacent orange pairs.