Rotting Oranges
Last Updated: March 28, 2026
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 figure out how many minutes it takes for every fresh orange to become rotten, or determine that some fresh oranges can never be reached.
The simultaneous spreading is the key detail here. All rotten oranges infect their neighbors at the same time during each minute. This is not a scenario where one rotten orange finishes spreading before another starts. They all act in parallel. That parallel, level-by-level expansion is what makes this a BFS problem rather than a DFS problem.
The other important detail is the -1 case. If any fresh orange is completely cut off from all rotten oranges by empty cells, it can never rot, and we return -1.
Key Constraints:
1 <= m, n <= 10-> The grid is at most 10x10 = 100 cells. Even an O(n^2 * m^2) brute force would handle this easily. But BFS is the natural fit for modeling simultaneous spreading.grid[i][j]is0,1, or2-> Only three possible values. No negative numbers or special values to worry about.
Approach 1: Brute Force Simulation
Intuition
The most direct approach is to literally simulate 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 catch is that we need to be careful about the order of updates. If we rot an orange and immediately use it to rot its neighbors in the same scan, we are letting rot spread too far in a single minute. So we need to separate "oranges that were already rotten at the start of this minute" from "oranges that just 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 approach works but redundantly scans the entire grid every minute. What if we only tracked the newly rotten oranges and processed just those?
Approach 2: Multi-source BFS
Intuition
Here is the key insight: rot spreading from multiple sources simultaneously is exactly what multi-source BFS does. Instead of running BFS from one starting point, we load all initial rotten oranges into the queue before starting. Then BFS processes them level by level. Each level corresponds to one minute of elapsed time.
Think of it like dropping multiple pebbles into a pond at the same time. Each pebble creates its own ripple, and the ripples expand outward simultaneously. The BFS queue naturally handles this. All the 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 track the count of fresh oranges. Every time we rot a fresh orange during BFS, we decrement the count. When BFS finishes, if any fresh oranges remain, those oranges were unreachable and we return -1.
Multi-source BFS works because it models the exact process described in the problem. All rotten oranges at a given minute are at the same "distance" from the initial rotten oranges. BFS naturally processes nodes in order of their distance from the source. By seeding the queue with all initial rotten oranges, we treat them as if they are all at distance 0. The first wave of neighbors is at distance 1 (minute 1), the next wave at distance 2 (minute 2), and so on.
This is the same principle behind finding shortest paths in an unweighted graph. Each edge has weight 1 (one minute), and BFS finds the shortest path from any source to any reachable node. The maximum of all those shortest paths is our answer.
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 (only if we actually rotted something).
- 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.