Rotting Oranges
MediumGraphs · Amazon
You are given an m x n grid where each cell is:
0: an empty cell1: a fresh orange2: a rotten orange
Every minute, each fresh orange that is directly up, down, left, or right of a rotten orange becomes rotten. All oranges that rot during a minute do so at the same time, and they only start spreading rot in the following minute. Empty cells do not carry rot.
Return the minimum number of minutes until no fresh orange is left. If the grid has no fresh oranges to begin with, return 0. If some fresh orange can never be reached by the rot, return -1.
Example 1
- Input:
- grid = [[2, 1, 0, 1], [1, 1, 1, 1], [0, 0, 1, 2]]
- Output:
- 2
- Explanation
- Both rotten oranges spread at once. In minute 1,
(0, 1)and(1, 0)rot from the top-left source, and(1, 3)and(2, 2)rot from the bottom-right one. In minute 2 those spread to(1, 1),(1, 2)and(0, 3), the last fresh oranges.
Example 2
- Input:
- grid = [[2, 1, 1], [0, 0, 0], [1, 1, 1]]
- Output:
- -1
- Explanation
- The bottom row is separated from the rotten orange by a row of empty cells, so those three oranges never rot.
Example 3
- Input:
- grid = [[0, 2, 0], [0, 0, 0]]
- Output:
- 0
- Explanation
- There are no fresh oranges at all, so no time needs to pass.
Constraints
m == grid.length,n == grid[i].length- 1 ≤
m,n≤ 10 grid[i][j]is0,1, or2