Rotten Oranges — Multi-source BFS on Grid

Problem Statement

You have a grid representing a box of oranges:

• 0 = empty cell
• 1 = fresh orange
• 2 = rotten orange

Every minute, any fresh orange adjacent (4-directionally) to a rotten orange becomes rotten.

Return the minimum number of minutes until no fresh orange remains. If impossible, return -1.

Constraints

• 1 <= grid.length, grid[0].length <= 10
• grid[i][j] is 0, 1, or 2

Example

Input:

grid = [[2,1,1],
        [1,1,0],
        [0,1,1]]

Output: 4

Explanation:

• Minute 1: oranges at (0,1) and (1,0) rot
• Minute 2: oranges at (0,2) and (1,1) rot
• Minute 3: orange at (2,1) rots
• Minute 4: orange at (2,2) rots

What the Interviewer Expects

1. Multi-source BFS — start BFS from ALL rotten oranges simultaneously (not one at a time).
2. Queue initialization — add all cells with value 2 to the queue at the start.
3. Track time — each BFS level = 1 minute.
4. Check completion — after BFS, scan grid for any remaining fresh oranges → return -1 if found.
5. Time: O(mn), Space: O(mn)

Follow-ups

1. What if rotting also spreads diagonally (8 directions)? How does time change?
2. What if some cells have "walls" that block rotting?
3. What if you can place one additional rotten orange anywhere — where should you place it to minimize total time?
4. Can you solve this with DFS? Why is BFS preferred here?