You are given grid, where each cell is one of:
0: empty,1: a fresh orange,2: a rotten orange.
Every minute, each fresh orange next to a rotten one (up, down, left or right) becomes rotten.
Return the number of minutes until no fresh orange is left. If some fresh orange can never rot,
return -1. If there are no fresh oranges to begin with, the answer is 0.
Example 1
- Input
- grid = [[1, 1, 0, 2], [0, 1, 1, 1], [2, 0, 0, 1]]
- Output
- 5
Example 2
- Input
- grid = [[2, 1], [0, 0], [1, 1]]
- Output
- -1
Example 3
- Input
- grid = [[0, 2], [2, 0]]
- Output
- 0
Constraints
- The grid has 1 to 100 rows and 1 to 100 columns.
- Every cell is
0,1or2.
Show the pattern
Graphs
Rot spreads one step per minute from every rotten orange at once, so the minute an orange rots is its distance from the nearest rotten one. A breadth-first search started from all the rotten oranges together measures exactly that, layer by layer.
See graphs in a visualiserShow the approach
Multi-source breadth-first search. Put every rotten orange in a queue and count the fresh ones.
Then, while fresh oranges remain and the queue isn't empty, play one minute: take every orange
that is in the queue at the start of the minute, and rot each fresh neighbour (set it to 2,
lower the fresh count, and queue it for the next minute). Add one to the minutes.
When the loop stops, return the minutes if no fresh orange is left, or -1 if some never rotted.
Each cell is queued at most once.
Time: O(rows · cols) · Space: O(rows · cols) for the queue