Rotting Oranges
On this page
Problem statement
A grid holds empty cells (0), fresh oranges (1) and rotten oranges (2). Every minute, each rotten orange rots the fresh oranges directly above, below, left and right of it. Return the number of minutes until no fresh orange remains, or −1 if that never happens.
The twist on plain BFS is that rot starts from many places at once. Putting all starting points in the queue together, a multi-source BFS, gives every cell its earliest time in one pass. Original problem: LeetCode 994.
Example

Input: [[2,1,1],
[1,1,0],
[0,1,1]]
Output: 4
Input: [[2,1,1],
[0,1,1],
[1,0,1]]
Output: -1 # the bottom-left orange is cut off
Constraints (assumed)
- 1 ≤ rows, cols ≤ 10.
- Each cell is 0, 1 or 2.
What this question tests
- BFS on a grid where BFS rounds equal time steps.
- Multi-source BFS: starting from every source at once.
- Detecting unreachable cells.
Questions to ask first
- Do diagonals spread rot? (Here: no, four directions.)
- What if there are no fresh oranges at the start? (Answer 0.)
- What if there are fresh oranges but no rotten ones? (Answer −1.)
- Can I modify the grid? (Here: yes; otherwise copy it.)
Try it yourself first
You have the full problem. Sketch your answer, then sign up free to read the complete walkthrough.
- The complete design, flow by flow, with pictures
- Deep dives into the hard parts
- What mid, senior and staff candidates are expected to say
- Full company question lists
Free forever. No card needed.