Rotting Oranges

You are given a grid where:

• 0 = empty,
• 1 = fresh orange,
• 2 = rotten orange.

Each minute, any fresh orange adjacent (up/down/left/right) to a rotten orange becomes rotten. Return the minimum minutes until no fresh oranges remain, or -1 if impossible.

Function signature

func OrangesRotting(grid [][]int) int

Inputs / outputs

• grid: rectangular grid.
• Return: minutes to rot all, or -1.

Example

grid = [[2,1,1],[1,1,0],[0,1,1]]
Output: 4

Constraints

• 1 <= rows, cols <= 100

Core idea (near-solution)

Use multi-source BFS from all rotten oranges simultaneously. Each BFS layer represents one minute of spread.

Invariant: oranges processed at the same BFS depth rot in the same minute.

Algorithm (step-by-step)

1. Enqueue all rotten oranges and count fresh ones.
2. BFS level-by-level; each level increments minutes.
3. When a fresh orange is reached, rot it and decrement the fresh count.
4. If fresh count reaches 0, return minutes; else return -1.

Correctness sketch

• Invariant: oranges processed at the same BFS depth rot in the same minute.
• BFS explores nodes in increasing distance from the sources.
• The first time a node is visited is its shortest distance.
• Therefore the recorded distance/level is optimal.

Trace (hand walkthrough)

Example input:
grid = [[2,1,1],[1,1,0],[0,1,1]]
Output: 4

Walk:
- minute 0: rotten at (0,0)
- minute 1: rot (0,1),(1,0)
- minute 2: rot (0,2),(1,1)
- minute 3: rot (2,1)
- minute 4: rot (2,2) -> done

Pitfalls to avoid

• Incrementing minutes when no fresh orange rots that round.
• Not handling the case of zero fresh oranges at the start.

Complexity

• Time: O(r*c)
• Extra space: O(r*c).

Implementation notes (Go)

• Initialize the queue with all rotten oranges (multi-source BFS).
• Track the count of fresh oranges and minutes by BFS levels.