Definition
- Multi-source BFS – all initially rotten cells are enqueued at time zero and advance in lockstep, so each BFS level represents one minute of rot spreading.
- Fresh counter – count fresh oranges up front and decrement each time one is rotted; if the counter reaches zero all oranges are rotten, otherwise some are unreachable.
- Level-by-level processing – process queue.size() cells per level, then increment the minute counter, ensuring each level adds exactly one minute.
- Impossible case – if fresh cells remain after the queue empties, return negative one.
- Time complexity – O(rows times cols) because each cell is enqueued at most once.
At the National Bank of India, a fraud contagion starts with some flagged accounts. Each minute the flag spreads to directly linked clean accounts. Rajesh seeds the BFS with all initially flagged accounts at once and counts how many minutes until every reachable account is flagged. If some account cannot be reached from any flagged source, the contagion can never finish.
Understanding the Concepts
What is the Rotting Oranges problem?
The problem gives a grid where each cell is 0 (empty), 1 (fresh orange), or 2 (rotten orange). Every minute, any fresh orange orthogonally adjacent to a rotten orange becomes rotten. The task is to return the minimum number of minutes until no fresh orange remains, or negative one if it is impossible.
This is a multi-source BFS problem because rot can start from multiple cells simultaneously.
package com.bank.service;
import java.util.LinkedList;
import java.util.Queue;
public class RottingOranges {
public int orangesRotting(int[][] grid) {
int rows = grid.length, cols = grid[0].length;
Queue<int[]> queue = new LinkedList<>();
int fresh = 0;
for (int r = 0; r < rows; r++) {
for (int c = 0; c < cols; c++) {
if (grid[r][c] == 2) queue.add(new int[]{r, c});
else if (grid[r][c] == 1) fresh++;
}
}
int minutes = 0;
int[][] directions = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
while (!queue.isEmpty() && fresh > 0) {
int size = queue.size();
for (int i = 0; i < size; i++) {
int[] cell = queue.poll();
for (int[] d : directions) {
int nr = cell[0] + d[0];
int nc = cell[1] + d[1];
if (nr >= 0 && nc >= 0 && nr < rows && nc < cols
&& grid[nr][nc] == 1) {
grid[nr][nc] = 2;
fresh--;
queue.add(new int[]{nr, nc});
}
}
}
minutes++;
}
return fresh == 0 ? minutes : -1;
}
public static void main(String[] args) {
int[][] grid = {
{2, 1, 1},
{1, 1, 0},
{0, 1, 1}
};
System.out.println("Minutes: " + new RottingOranges().orangesRotting(grid));
}
}
Minutes: 4
Why is multi-source BFS the right approach?
Multi-source BFS is correct because all rotten cells spread rot simultaneously. If we ran a separate BFS from each rotten cell, we could not measure the combined spread time correctly. By seeding the queue with all rotten cells at time zero, the BFS naturally processes them in lockstep: level 0 contains all initially rotten cells, level 1 contains all cells that rot at minute 1, and so on. The number of BFS levels is the answer.
package com.bank.service;
public class WhyMultiSourceBFS {
// Single-source BFS from each rotten cell:
// - Would need to track which cell rots first at each position
// - Complex and error-prone
//
// Multi-source BFS (all rotten cells at once):
// - All sources advance in lockstep
// - Level count directly gives the time
// - Simple and correct
public static void main(String[] args) {
System.out.println("Multi-source BFS processes all rotten cells in lockstep.");
System.out.println("Level 0: all initially rotten cells.");
System.out.println("Level k: all cells that rot at minute k.");
}
}
How does the fresh counter detect the impossible case?
Instead of rescanning the entire grid after BFS to check for remaining fresh oranges, we count fresh oranges up front and decrement the counter each time we rot one. If the counter reaches zero, all fresh oranges were rotted. If it is still positive after the queue empties, some fresh orange was unreachable and we return negative one.
package com.bank.service;
public class FreshCounterDemo {
public static void main(String[] args) {
// Grid where one fresh orange is unreachable
int[][] grid = {
{2, 1, 1},
{0, 0, 0},
{1, 0, 0}
};
// fresh = 3 initially
// BFS from (0,0) rots (0,1) and (0,2) => fresh = 1
// Queue empties, but fresh = 1 => return -1
System.out.println("Minutes: " + new RottingOranges().orangesRotting(grid));
}
}
Minutes: -1
How is this different from Number of Islands?
| Feature | Number of Islands | Rotting Oranges |
|---|---|---|
| Goal | count connected components | minimum time for spread |
| Sources | each unvisited land cell | all rotten cells at once |
| BFS type | single-source per component | multi-source from all rotten |
| Counting | increment per flood fill | level count gives time |
| Impossible case | none (just count) | fresh > 0 after BFS |
package com.bank.service;
public class IslandsVsRotting {
public static void main(String[] args) {
System.out.println("Islands: single-source DFS/BFS per component, count components.");
System.out.println("Rotting: multi-source BFS, count levels for time.");
}
}
What are the edge cases?
Edge cases include a grid with no fresh oranges (return 0 immediately), a grid with no rotten oranges but some fresh ones (return negative one), a single-cell grid, and a grid where all cells are empty.
package com.bank.service;
public class RottingEdgeCases {
public static void main(String[] args) {
RottingOranges solver = new RottingOranges();
// No fresh oranges: already done
int[][] noFresh = {{2, 2}, {2, 0}};
System.out.println("No fresh: " + solver.orangesRotting(noFresh));
// No rotten, but fresh exist: impossible
int[][] noRotten = {{1, 1}, {1, 1}};
System.out.println("No rotten: " + solver.orangesRotting(noRotten));
// All empty: no fresh => 0
int[][] empty = {{0, 0}, {0, 0}};
System.out.println("All empty: " + solver.orangesRotting(empty));
}
}
No fresh: 0
No rotten: -1
All empty: 0
What are common mistakes?
The most common mistake is incrementing the minute counter even when no fresh orange was rotted in a level, which overcounts by one. Another mistake is not checking fresh > 0 in the while loop condition, which causes the BFS to continue processing empty levels and increment minutes after all oranges are already rotten.
Wrong code that overcounts:
// WRONG: increments minutes even when no orange was rotted
while (!queue.isEmpty()) {
int size = queue.size();
for (int i = 0; i < size; i++) {
// ... process cell
}
minutes++; // BUG: increments even for the last level with no new rot
}
Correct code:
// CORRECT: only process while fresh > 0
while (!queue.isEmpty() && fresh > 0) {
int size = queue.size();
for (int i = 0; i < size; i++) {
// ... process cell, decrement fresh
}
minutes++;
}
When should you use multi-source BFS?
Use multi-source BFS whenever multiple sources spread simultaneously and you need the time for the spread to complete. Examples include fire spreading from multiple starting points, virus spreading through a network, and shortest distance from any source to every cell. The key insight is that all sources at time zero advance in lockstep, so the BFS level directly gives the time.
package com.bank.service;
public class MultiSourceBFSUseCases {
// Banking use case: fraud contagion
// - Multiple compromised accounts flagged at time zero
// - Each minute, flag spreads to linked clean accounts
// - Multi-source BFS gives the time to flag every reachable account
public static void main(String[] args) {
System.out.println("Multi-source BFS use cases:");
System.out.println(" 1. Rotting oranges / fire spread");
System.out.println(" 2. Fraud contagion in bank networks");
System.out.println(" 3. Shortest distance from any source");
System.out.println(" 4. Virus spread in computer networks");
}
}
What should a senior engineer know?
A senior engineer knows that multi-source BFS is equivalent to adding a virtual super-source connected to all real sources with zero-cost edges. They also know that the fresh counter is cleaner than rescanning the grid, and that the time complexity is O(rows times cols) because each cell is enqueued at most once. In production at National Bank of India, the fraud contagion model uses multi-source BFS to compute how quickly a compromise can spread through the account network, with the fresh counter flagging accounts that no compromised source can ever reach.
package com.bank.service;
public class SeniorRottingNotes {
// Virtual super-source concept:
// Imagine a node S connected to all initially rotten cells with 0-cost edges.
// BFS from S gives the same result as multi-source BFS.
//
// Why fresh counter > grid rescan:
// - O(1) check vs O(rows * cols) rescan
// - Cleaner code, fewer bugs
public static void main(String[] args) {
System.out.println("Senior insights:");
System.out.println(" Multi-source BFS = virtual super-source + regular BFS");
System.out.println(" Fresh counter avoids O(rows*cols) rescan");
}
}
Visual Overview
Rotting Oranges: Multi-Source BFS
Initial grid: After minute 1: After minute 2:
┌───┬───┬───┐ ┌───┬───┬───┐ ┌───┬───┬───┐
│ 2 │ 1 │ 1 │ │ 2 │ 2 │ 1 │ │ 2 │ 2 │ 2 │
├───┼───┼───┤ ├───┼───┼───┤ ├───┼───┼───┤
│ 1 │ 1 │ 0 │ │ 2 │ 1 │ 0 │ │ 2 │ 2 │ 0 │
├───┼───┼───┤ ├───┼───┼───┤ ├───┼───┼───┤
│ 0 │ 1 │ 1 │ │ 0 │ 1 │ 1 │ │ 0 │ 1 │ 1 │
└───┴───┴───┘ └───┴───┴───┘ └───┴───┴───┘
After minute 3: After minute 4:
┌───┬───┬───┐ ┌───┬───┬───┐
│ 2 │ 2 │ 2 │ │ 2 │ 2 │ 2 │
├───┼───┼───┤ ├───┼───┼───┤
│ 2 │ 2 │ 0 │ │ 2 │ 2 │ 0 │
├───┼───┼───┤ ├───┼───┼───┤
│ 0 │ 2 │ 1 │ │ 0 │ 2 │ 2 │
└───┴───┴───┘ └───┴───┴───┘
fresh = 0 => return 4
Queue levels:
Level 0 (t=0): [(0,0)] all initially rotten
Level 1 (t=1): [(0,1), (1,0)] fresh adjacent to level 0
Level 2 (t=2): [(0,2), (1,1)] fresh adjacent to level 1
Level 3 (t=3): [(1,2 skip), (2,1)] fresh adjacent to level 2
Level 4 (t=4): [(2,2)] last fresh orange
Key Takeaway
Rotting Oranges is a multi-source BFS problem where all initially rotten cells are seeded in the queue at time zero and spread rot in lockstep. Each BFS level represents one minute, and the number of levels is the minimum time to rot every reachable fresh orange. If any fresh orange remains unreachable after the queue empties, the answer is negative one.
The fresh counter is the clean way to detect the impossible case. Instead of rescanning the entire grid after BFS, count fresh oranges up front and decrement each time one is rotted. When the counter reaches zero, all fresh oranges were rotted. When the queue empties with the counter still positive, some orange was unreachable.
The key insight interviewers want is why multi-source BFS is correct: because all sources advance together in lockstep, the level count directly gives the time for the last orange to rot. Running separate BFS from each rotten cell would not measure the combined spread time correctly. This is equivalent to imagining a virtual super-source connected to all initially rotten cells.
At the National Bank of India, Rajesh used this model for fraud contagion. Some accounts were flagged as compromised, and each minute the flag spread to directly linked clean accounts. Multi-source BFS computed the minimum time to flag every reachable account, and the fresh counter identified accounts that no compromised source could ever reach, which needed manual investigation.
Remember one sentence: seed multi-source BFS with all rotten cells at time zero, count levels for minutes, and use a fresh counter to detect unreachable oranges.
---