654. Spreading Rot
A grocer stores fruit in a rectangular grid of trays. A tray holds 0 when it is empty, 1 when it holds fresh fruit, and 2 when it holds rotten fruit. Every minute, each fresh tray that is directly above, below, left or right of a rotten tray becomes rotten as well; rot never crosses empty trays and never moves diagonally.
Return the minimum number of minutes after which no tray holds fresh fruit. If there is no fresh fruit at the start, return 0. If some fresh tray can never become rotten, return -1. Your solution should run in O(R * C) time and use O(R * C) extra space.
Example 1
- Input:
- grid = [[2,1,1],[1,1,0],[0,1,1]]
- Output:
- 4
- Explanation:
The rot spreads outward one step per minute from the top-left corner, and the last fruit, at the bottom right, rots after 4 minutes.
Example 2
- Input:
- grid = [[2,1,0,1],[0,0,0,1]]
- Output:
- -1
- Explanation:
The fruit at the right edge is cut off by empty slots, so it can never rot and the answer is -1.
Example 3
- Input:
- grid = [[0,2],[0,0]]
- Output:
- 0
- Explanation:
There is no fresh fruit to begin with, so the answer is 0.
Constraints
1 ≤ R, C ≤ 350
grid[i][j] is 0, 1 or 2
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 1,600 msC++ 400 msJava 800 msJavaScript 800 msTypeScript 800 ms
Expected complexity
- Time
- O(R * C)
- Space
- O(R * C)