97. Rotting Oranges
Time advances in simultaneous rounds. During a minute, oranges that were already rotten at its beginning rot neighboring fresh oranges in the four orthogonal directions.
A newly rotten orange cannot spread again during that same minute. Return -1 if some fresh orange can never be reached, and follow the contract for an already-complete grid.
Example 1
Input
[[2,1,1],[1,1,0],[0,1,1]]
Output
4
Explanation: Layers reached at minutes 1,2,3,4 exhaust the six fresh oranges; the bottom-right orange is farthest from the initial source.
Example 2
Input
[[2,0,1]]
Output
-1
Explanation: The empty middle cell separates the only fresh orange from every source.
Example 3
Input
[[0,2]]
Output
0
Explanation: There are no fresh oranges at minute zero.
Constraints
0 <= rows, columns <= 100- Cells are 0 (empty), 1 (fresh) or 2 (rotten). The grid is rectangular.
Hints
Hint 1
Imagine all initial rotten cells as one combined starting frontier. What graph edge represents one minute?
Hint 2
Newly discovered cells should act in the next minute. How do you keep the two frontiers separate in one queue?
Hint 3
Freeze the queue size for each layer and mark a neighbor rotten before enqueueing it. Track remaining fresh cells.
Submissions
Your recent submissions for this problem.
Checking sign-in…
Discussion
Ask a question or share an approach. Posts are public; avoid personal information and mark solution spoilers clearly.
No discussion yet. Start the conversation with a question about this problem.
Checking sign-in…
Run your code to check the sample cases, or submit it to check the full validation suite.
Four minute propagation
[[2,1,1],[1,1,0],[0,1,1]]
4