Rotting Oranges

Problem Grid cells are empty (0), fresh orange (1), or rotten orange (2). Every minute, rotten oranges rot 4-directionally adjacent fresh ones. Return the minutes until no fresh orange remains, or -1 if some can never rot.

Input / Output

• Input: int grid m x n. Output: minutes or -1.

Constraints

• m, n <= 10; but the technique (multi-source BFS) must be articulated for large grids; O(m*n).

Example

• [[2,1,1],[1,1,0],[0,1,1]] → 4; [[2,1,1],[0,1,1],[1,0,1]] → -1 (bottom-left orange unreachable).

Expected approach

• Multi-source BFS: enqueue ALL initially rotten oranges at level 0, count fresh; process level by level, rotting neighbors and decrementing the fresh count; answer = levels elapsed when fresh hits 0, else -1. The multi-source seeding (vs running BFS per rotten orange) is the key idea; equivalently "shortest distance from the nearest source". O(m*n) time/space.