Rotting Oranges

Rotting Oranges is LeetCode problem 994, commonly asked in Amazon interviews with tags Array, BFS, and Matrix.[1][3][10]

Problem Statement

You are given an m x n grid where each cell has one of three values:

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

Every minute, any fresh orange adjacent (4-directionally: up, down, left, right) to a rotten orange becomes rotten. Return the minimum minutes until no fresh oranges remain, or -1 if impossible.[3][5][10][1]

Examples

Example 1

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

Minute 0: [[2,1,1],[1,1,0],[0,1,1]]
Minute 1: [[2,2,1],[1,2,0],[0,1,1]]
Minute 2: [[2,2,2],[1,2,0],[0,2,1]]
Minute 3: [[2,2,2],[2,2,0],[0,2,1]]
Minute 4: [[2,2,2],[2,2,0],[0,2,2]][5][1]

Example 2

Input: grid = [[2,1,1],[1,1,0],[0,1,1]] (wait, same as above but output differs in some sources—no, standard is 4)
Standard Example 2: grid = [[2,1,1],[0,1,1],[1,0,1]]
Output: -1 (isolated fresh oranges unreachable)[1][3]

Example 3

Input: grid = [[0,2]]
Output: 0 (no fresh oranges)[1]

Constraints

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