Rotting Oranges
Understanding the Problem
We have a grid of oranges. Rotten oranges spread rot to their fresh neighbors every minute, all at the same time. We need to find how many minutes it takes for every fresh orange to become rotten, or determine that some fresh oranges can never be reached.
The spreading is simultaneous. All rotten oranges infect their neighbors during the same minute, not one orange finishing its spread before another begins. That parallel, level-by-level expansion is what makes this a BFS problem rather than a DFS problem, since BFS expands outward one ring at a time and each ring maps to one minute.
The -1 case covers fresh oranges that are cut off from every rotten orange by empty cells. Such an orange can never rot, so we return -1.
Key Constraints:
1 <= m, n <= 10-> The grid is at most 10x10 = 100 cells, so even an O((m*n)^2) brute force passes. That headroom lets us start with a direct simulation before optimizing to BFS.grid[i][j]is0,1, or2-> Three possible values, so we can overwrite a cell to2as a visited marker without losing information.
Approach 1: Brute Force Simulation
Intuition
Simulate exactly what the problem describes. Each minute, scan the entire grid and find every fresh orange adjacent to a rotten orange. Mark those fresh oranges as rotten. Repeat until nothing changes. Count the minutes.
The order of updates matters. If we rot an orange and then immediately use it to rot its neighbors in the same scan, rot spreads more than one ring in a single minute, which overcounts how fast it travels. To prevent that, we record which cells should rot during the scan but apply all the updates only after the scan finishes. This separates oranges that were rotten at the start of the minute from oranges that became rotten this minute.
Algorithm
- Count all fresh oranges in the grid.
- Initialize
minutes = 0. - In each round, scan the entire grid. For each fresh orange adjacent to a rotten orange, mark it for rotting.
- After the full scan, apply all the rotting marks. Decrement the fresh count for each newly rotten orange.
- If any oranges rotted this round, increment
minutesand repeat. If none rotted, stop. - If fresh oranges remain, return
-1. Otherwise, returnminutes.
Example Walkthrough
Code
- Time Complexity: O((m n)^2). In the worst case, rot spreads one cell at a time across the grid. That means up to O(m n) rounds, each scanning the full grid at O(m * n).
- Space Complexity: O(m n). We allocate a
toRotboolean grid each round of size m n.
This rescans the whole grid every minute, even cells that rotted long ago. The next approach tracks only the newly rotten oranges and processes each cell once.
Approach 2: Multi-source BFS
Intuition
Rot spreading from multiple sources at once is what multi-source BFS models. Instead of running BFS from a single starting point, we load all initial rotten oranges into the queue before the search begins. BFS then processes them level by level, and each level corresponds to one minute of elapsed time.
This is like dropping several pebbles into a pond at the same instant. Each pebble starts its own ripple, and the ripples expand outward together. The queue produces the same effect: all initial rotten oranges go in first (level 0), then their fresh neighbors become rotten (level 1), then those neighbors' fresh neighbors (level 2), and so on.
We also keep a count of fresh oranges and decrement it each time one rots during the search. When the queue empties, any remaining fresh oranges were never reached, so we return -1.
The minute at which an orange rots equals its shortest distance, in number of steps, to the nearest initial rotten orange. Seeding the queue with every initial rotten orange treats them all as distance 0. BFS dequeues cells in nondecreasing order of distance, so the first time it reaches a fresh cell is along a shortest path, and that distance is the minute the cell rots. No later path can rot it sooner.
This is the standard shortest-path argument for an unweighted graph where each edge costs one minute. The total time to rot everything is the maximum over all reachable cells of that shortest distance, which is the depth of the last BFS level that rots an orange.
Algorithm
- Scan the grid. Add all rotten oranges to a queue. Count all fresh oranges.
- If there are no fresh oranges, return
0immediately. - Run BFS. For each level (minute), process all oranges currently in the queue.
- For each rotten orange, check its 4 neighbors. If a neighbor is fresh, mark it rotten, decrement the fresh count, and add it to the queue.
- After processing a full level, increment the minute counter, but only when that level rotted at least one orange.
- When the queue is empty, check: if
fresh == 0, returnminutes. Otherwise, return-1.
Example Walkthrough
Code
- Time Complexity: O(m * n). We scan the grid once to initialize, then BFS visits each cell at most once with O(1) work per cell.
- Space Complexity: O(m * n). The queue can hold at most all cells in the grid.