Graphs · 074Medium
Rotting Oranges
In an m x n grid, 0 is empty, 1 is a fresh orange and 2 is rotten. Each minute, every fresh orange adjacent (4-directionally) to a rotten one becomes rotten. Return the minutes until no fresh orange remains, or -1 if that is impossible.
Constraints
- 1 <= m, n <= 10
- grid[i][j] is 0, 1 or 2.
Examples
orangesRotting([[2,1,1],[1,1,0],[0,1,1]]) -> 4 orangesRotting([[2,1,1],[0,1,1],[1,0,1]]) -> -1 // one is unreachable orangesRotting([[0,2]]) -> 0 // nothing fresh orangesRotting([[0]]) -> 0 // no oranges at all orangesRotting([[1]]) -> -1 // fresh, and nothing can ever rot it orangesRotting([[2,2],[1,1]]) -> 1 // both rot in the same minute
Edge cases
- No fresh oranges at the start returns 0, not -1.
- A fresh orange with no rotten neighbor ever returns -1.
Show the target complexity (spoiler)
- Naive
- Running a separate BFS per rotten orange overcounts the elapsed time.
- Target
- O(m * n) time — multi-source BFS seeding the queue with EVERY rotten orange, counting levels as minutes.
Solve it
By hand, in your editor. The runner checks answers and timing.
git clone https://github.com/sarmadkung/optimal-round cd optimal-round # open problems/08-graphs/074-rotting-oranges.js ./practice c 074