Minutes Until Every Orange Rots
You are given a grid grid of numbers. Each cell holds one of three values:
0— the cell is empty,1— the cell holds a fresh orange,2— the cell holds a rotten orange.
Every minute, each fresh orange that is directly up, down, left or right of a rotten orange becomes rotten. Diagonal cells do not count. All of these changes happen at the same time.
Return the number of minutes until no fresh orange is left. If some fresh orange can never become rotten, return -1.
Note
- If the grid has no fresh orange at the start, the answer is
0.
Hint: put every rotten orange in a queue at the start, and spread out from all of them together, one minute (one layer) at a time.
Examples
Example 1
- Input:
- [[2,1,0,1],[0,1,1,1],[1,0,1,2]]
- Output:
- -1
The orange in the bottom-left corner has an empty cell above it and an empty cell to its right. No rotten orange can ever reach it.
Example 2
- Input:
- [[1,1,1],[1,0,1],[2,0,1]]
- Output:
- 6
The rot starts in the bottom-left corner and moves up the left side, across the top and down the right side, one cell each minute. The last orange, in the bottom-right corner, rots at minute 6.
Example 3
- Input:
- [[0,2,0],[0,0,0]]
- Output:
- 0
There is no fresh orange at the start, so no time is needed.
Constraints
1 <= grid.length <= 101 <= grid[i].length <= 10, and every row has the same length.grid[i][j]is0,1or2.
Run checks your code against the 3 examples. Submit checks it against all 203 tests and needs a free account. You can also try ideas in the free JavaScript or Python compiler.