Rotting Oranges
Medium
You are given an m x n grid where:
- 0 represents an empty cell.
- 1 represents a fresh orange.
- 2 represents a rotten orange.
Every minute, any fresh orange that is 4-directionally adjacent to a rotten orange becomes rotten.
Return the minimum number of minutes that must elapse until no cell has a fresh orange.
If it is impossible for all fresh oranges to become rotten, return -1.
Example 1
Input
grid = [
[2, 1, 1],
[1, 1, 0],
[0, 1, 1]
]Output
4
Explanation
The rotten oranges spread to adjacent fresh oranges minute by minute.
It takes 4 minutes for all fresh oranges to become rotten.
Example 2
Input
grid = [
[2, 1, 1],
[0, 1, 1],
[1, 0, 1]
]Output
-1
Explanation
The fresh orange in the bottom-left corner can never be reached by a rotten orange.
Therefore, not all oranges can become rotten.
Constraints
1 <= m
n <= 10
grid[i][j] is 0
1
or 2.
0 represents an empty cell.
1 represents a fresh orange.
2 represents a rotten orange.
Hints:
Hint 1
Start by finding all rotten oranges and put them into a queue.
Hint 2
Process all rotten oranges level by level.
Each level represents one minute.
Auto
Loading editor...
Input
Expected Output