Rotting Oranges Time

Simulate the spread of rot through a grid and return the minutes until all oranges rot, or -1 if impossible.

bfs grid simulation queue

You are given a 2D list `grid` of integers where:
- `0` = empty cell,
- `1` = fresh orange,
- `2` = rotten orange.

Every minute, a fresh orange that is 4-directionally adjacent (up, down, left, right) to a rotten orange becomes rotten.

Write a function `oranges_rotting(grid)` that returns the minimum number of minutes that must elapse until no cell contains a fresh orange. If it is impossible for all fresh oranges to become rotten, return `-1`.

Your solution should be efficient for grids up to 100×100 cells.

Constraints

- `1 <= rows, cols <= 100`
- Each cell is `0`, `1`, or `2`.
- There is at least one cell.
- Time complexity should be O(rows × cols).

Example

```python
print(oranges_rotting([[2,1,1],[1,1,0],[0,1,1]]))  # 4

print(oranges_rotting([[2,1,1],[0,1,1],[1,0,1]]))  # -1

print(oranges_rotting([[0,2]]))  # 0

print(oranges_rotting([[1,1,1],[1,0,1],[1,1,1]]))  # -1
```

25 points ~25 min

Recent Submissions

No submissions yet — hit Run Tests to try!

Hints

Perform BFS starting from all initially rotten oranges at time 0.

Track the number of fresh oranges; decrement each time you rot one.

The answer is the maximum BFS level reached, unless fresh oranges remain (then -1).

Test Results

Press Ctrl+Enter or click Run Tests to execute your code.