Rot spreads outward one layer per minute from every rotten orange at once. That "expand by layers" behavior is exactly what BFS does, run from many sources simultaneously.
Each grid cell is a node; 4-directional neighbors are edges. BFS visits nodes in waves: everything at distance 1 before anything at distance 2. Here one wave = one minute of rot spreading.
Seed the queue with all rotten oranges up front (that's the "multi-source" trick), then expand level by level.
2 = rotten, 1 = fresh, 0 = empty-1int orangesRotting(vector<vector<int>>& grid) {
int rows = grid.size(), cols = grid[0].size();
queue<pair<int,int>> q;
int fresh = 0;
// seed queue with every rotten orange (multi-source)
for (int r = 0; r < rows; r++)
for (int c = 0; c < cols; c++) {
if (grid[r][c] == 2) q.push({r, c});
else if (grid[r][c] == 1) fresh++;
}
int minutes = 0;
int dr[] = {-1,1,0,0}, dc[] = {0,0,-1,1};
while (!q.empty() && fresh > 0) {
int sz = q.size();
while (sz--) { // process one full layer
auto [r, c] = q.front(); q.pop();
for (int d = 0; d < 4; d++) {
int nr = r + dr[d], nc = c + dc[d];
if (nr < 0 || nc < 0 || nr >= rows || nc >= cols) continue;
if (grid[nr][nc] != 1) continue;
grid[nr][nc] = 2; // rot it
fresh--;
q.push({nr, nc});
}
}
minutes++;
}
return fresh == 0 ? minutes : -1;
}Every cell is enqueued and dequeued at most once, and each has 4 neighbor checks.
Worst case the queue holds every cell (all oranges rotten at once).
Number of BFS levels equals the minutes returned. Level order is what makes BFS give shortest distance.
sz = q.size() snapshot is the key to counting layers. Freeze the size, drain exactly that many, then bump the minute counter.2 doubles as your visited marker, so no separate visited set.