994. Rotting Oranges - Detailed Explanation
Problem statement
We have a grid (matrix) where each cell can be one of three values:
0is an empty cell (no orange).1is a fresh orange.2is a rotten orange.
Every minute, any fresh orange that is 4-directionally adjacent (up, down, left, or right) to a rotten orange becomes rotten. The task is to determine the minimum number of minutes required for all fresh oranges to become rotten. Sometimes it is impossible for all oranges to rot, because some fresh oranges are completely isolated from any rotten orange. In that case the answer should be -1.
Example 1
Input: [[2,1,1],[1,1,0],[0,1,1]]
Output: 4
Explanation: In this 3x3 grid, the rot spreads from the initially rotten orange to all others in 4 minutes. Starting with one rotten orange at (0,0), each minute it contaminates adjacent fresh ones until all reachable oranges are rotten.
Example 2
Input: [[2,1,1],[0,1,1],[1,0,1]]
Output: -1
Explanation: The fresh orange at (2,0) remains isolated by empty cells and can never rot. Hence, not all fresh oranges can become rotten.
Example 3
Input: [[0,2]]
Output: 0
Explanation: There are no fresh oranges to begin with, so the time required is 0 minutes.
Constraints
m == grid.length,n == grid[i].length1 <= m, n <= 10(grid dimensions are at most 10x10)grid[i][j]is only0,1, or2.
Which pattern this problem belongs to
This question is an instance of the Graphs pattern, in its multi-source form. Breadth-first search (BFS) is a traversal that visits every cell one step away, then every cell two steps away, and so on. Each BFS layer here equals one minute of rotting.
Design Gurus teaches this exact problem in the Rotting Oranges lesson of Grokking the Amazon Coding Interview. The course Grokking the Coding Interview teaches the graph pattern itself. Our guide to recurring LeetCode patterns also shows how often grid traversal appears in interviews. Rotting Oranges sits on the Blind 75 list as well, so practice it until the template comes back without effort.
Hints to solve the problem
- Think of the rotting process as a spreading infection. One rotten orange contaminates its neighbors over time, the way an infection spreads in waves.
- A breadth-first search (BFS) approach is ideal here. BFS processes nodes level by level, which matches minute by minute spreading. Each minute corresponds to one level of BFS propagation.
- Use a queue to hold the oranges that will rot others in the next minute. Enqueue all rotten oranges first, so the traversal starts from several points at once. Then process every orange in the queue, rot their fresh neighbors, and enqueue those newly rotten oranges for the next round.
- Track the total count of fresh oranges. Decrement the count each time a fresh orange rots. The count tells you when every orange has rotted, and it also detects oranges that stay fresh, which means the answer is
-1.
Approach 1: brute force (inefficient)
Idea: simulate the rotting process minute by minute. In each iteration, scan the entire grid and find every fresh orange adjacent to a rotten orange. Rot all of those fresh oranges at the same time. Repeat until no new orange becomes rotten during an iteration. The number of iterations is the time taken. If fresh oranges remain when the process stops, no rotten orange can reach them, so return -1.
This simulation literally iterates the grid minute by minute, rotting the fresh oranges next to rotten ones. Rot the oranges for each minute simultaneously, usually by writing the next state into a copy of the grid. Without that copy, an orange that rots at minute k would immediately rot its neighbors inside the same iteration. The loop continues until every orange is rotten or until an iteration changes nothing. If any fresh orange remains at that point, the answer is -1.
Why this approach is inefficient
The spread can take many minutes, and each minute costs a full grid scan. For a grid of size m × n and k minutes of rotting, the time complexity is about O(k × m × n). In the worst case the oranges rot one after another rather than concurrently, so k approaches m × n. That raises the cost to roughly O((m × n)^2), which is very slow on larger grids. Copying the grid state for each iteration adds O(m × n) space. The method is correct and it clears the small grids in the constraints, but it is not optimal.
Approach 2: optimal BFS approach
Idea: multi-source BFS answers the question far more efficiently. Treat every initially rotten orange as a starting point, then spread the rot outward in waves. BFS processes nodes in layers, and each layer corresponds to one minute. The oranges that rot after one minute form the first layer, those that rot after two minutes form the next, and so on. Every orange therefore rots at the earliest minute possible.
How it works
Think of the grid as a graph where each cell is a vertex. Edges connect cells that are adjacent up, down, left, or right. All initially rotten oranges are enqueued before the traversal starts. Then:
- Initialization: enqueue the coordinates of every rotten orange and set a
minutescounter to 0. Count the total number of fresh oranges at the start. If there are no fresh oranges at all, return 0 immediately, because nothing has to rot. - BFS traversal: while the queue is not empty, process every orange in the queue for the current minute. Those are the oranges that are rotten at this time. For each one, look at its 4 neighbors. If a neighbor is a fresh orange (value
1), turn it rotten (value2), decrement the fresh count, and add that neighbor to the list of oranges that will be rotten in the next minute. - Increment time: once the entire queue level is processed, increment the
minutescounter and refill the queue with the newly rotten oranges. The traversal has now moved to the next minute of spread. - Continue BFS: repeat until no fresh orange is left to rot or the queue becomes empty.
If the queue empties while fresh oranges remain (fresh_count > 0), the rot never reached them, because they are isolated. Return -1 in that case. Otherwise the minutes counter holds the minimum time the process took. One nuance deserves attention. If you count minutes on each layer change, the loop ends one increment too late, so some implementations return minutes - 1. The implementations below increment after each layer and then return minutes - 1, which removes that extra step.
Why this is efficient
BFS makes each orange rot at the earliest possible time, and each cell is visited at most once, as it turns from fresh to rotten. The time complexity is therefore O(m × n), since each cell is processed a constant number of times. The space complexity is also O(m × n) in the worst case, because the queue can hold every orange when they all rot at about the same time. That is much better than the brute force simulation. Multi-source BFS is the standard optimal solution for this problem.
Code implementations
Python implementation
Explanation: the Python code uses a queue (deque) to run BFS. We first enqueue all rotten oranges and count the fresh ones. Then we loop minute by minute, where each loop iteration represents one minute, and process every orange that is rotten at that time. For each rotten orange we rot its fresh neighbors and enqueue those neighbors for the next round. We increment the minutes counter after each layer. At the end, we return -1 if any fresh orange remains. Otherwise we return minutes - 1, because the loop increments minutes one extra time after the last set of oranges rotted.
Java implementation
Explanation: the Java code uses a LinkedList as the queue for BFS. We first add all rotten oranges to the queue and count the fresh ones. Then we run a BFS loop. Each iteration represents one minute of time, so we process every element currently in the queue. Those are the oranges that are rotten at the start of this minute. For each rotten orange we check its four neighbors. If a neighbor is fresh, we rot it by setting it to 2, decrement the fresh count, and enqueue that neighbor. We increment the minutes counter after processing one layer of BFS. In the end, we return -1 if there are still fresh oranges left, and otherwise minutes - 1 as the time taken. We subtract 1 because the loop performs one extra increment in the last iteration, where no new orange got rotted.
Complexity analysis
Approach 1 (brute force): let m be the number of rows and n the number of columns. In the worst case, the grid scan repeats for each minute of rotting. If the process takes k minutes to finish, the time complexity is O(k · m · n). In the worst scenario the rot spreads one orange at a time, so k can reach m·n as the rot propagates to each cell sequentially. That makes the complexity about O((m·n)^2), which is extremely slow for large grids. The space complexity is O(m · n), because a copy of the grid tracks the updates for each minute without disturbing the ongoing process.
Approach 2 (BFS): we perform a single BFS traversal of the grid. Each cell is enqueued and dequeued at most once, when it becomes rotten, and we check a constant number of neighbors, four, for each cell. The time complexity is therefore O(m · n). The space complexity is also O(m · n) in the worst case, because the queue can hold every orange if they all become rotten in the same wave.
Common mistakes and edge cases
-
Forgetting the multi-source start: a common mistake is to enqueue only one rotten orange, or to process the rotten oranges one by one. Every orange that is rotten at the start belongs in the queue together, treated as a simultaneous source. Missing this produces incorrect results or an overestimated time.
-
Incorrect time calculation: off-by-one errors in the minute counter are easy to make. If you increment the counter after processing a layer of BFS, the final answer is
minutes - 1once all oranges are rotten, because the last increment happens after the final fresh orange rots. Another strategy increments minutes at the start of each round except the first, which aligns the count correctly. -
Not handling the no-fresh case: zero fresh oranges at the beginning means the answer is 0, since no time is needed. Check for that before starting the BFS. In Example 3, there were no fresh oranges initially, so the output was 0.
-
Isolated oranges not detected: if any fresh orange remains after the process, you must return -1. Returning the minute count while fresh oranges are left is wrong. Make your solution check for remaining fresh oranges at the end. A grid like Example 2 must yield -1, because the rot never reached one fresh orange.
-
Updating the grid in place during brute force: a naive in-place update rots oranges inside the same iteration, before their minute arrives. Compute the next state on a separate grid instead, or mark the changes and apply them after the scan. This extra bookkeeping is one reason the brute force method is not ideal.
Alternative variations and related problems
-
Diagonal or other spread rules: a variation could let oranges rot diagonally, with 8-directional adjacency, or require more than one minute to spread to a neighbor. BFS still solves it, with different neighbor directions or processing rules. Diagonal spread simply adds the 4 extra directions to the traversal. If spreading takes longer, mark each orange with the time it will rot and process the oranges in increasing time order, as weighted BFS or Dijkstra's algorithm would on a grid.
-
Zombie in a Matrix: this known variant uses 1 for a human and 2 for a zombie, and the zombies infect adjacent humans each hour. The BFS approach is the same, and only the story changes. The goal is the number of hours until every human is infected, or a verdict that it cannot happen.
-
Walls and Gates (LeetCode 286): in this related problem, 0 represents gates and each empty room is filled with the distance to the nearest gate. All gates serve as simultaneous BFS sources, exactly as all rotten oranges do here. The multi-source BFS pattern is the same.
-
Matrix distance transform (01 Matrix, LeetCode 542): that problem asks for the distance from each cell to the nearest 0 in a binary matrix. All zeros are enqueued as sources, and BFS fills in the distances for the ones. This is again a multi-source BFS scenario.
-
Flood fill and fire spread problems: many grid-based spread simulations use a similar approach, such as fire moving through a forest or an infection moving through a network. When the rules allow simultaneous spreading to neighbors in discrete time steps, BFS is usually the ideal way to compute the minimum time or the extent of propagation.
Keep a running list of the grid questions you have solved with this template. The short summary of common LeetCode patterns also helps you name the pattern behind a new question before you start coding.
GET YOUR FREE
Coding Questions Catalog
$99
$197
$72
