Rotting Oranges

Implement minutes_until_all_rotten(grid: list[list[int]]) -> int.

The grid contains 0 for an empty cell, 1 for a fresh orange, and 2 for a rotten orange. Each minute, every fresh orange directly above, below, left, or right of a rotten orange becomes rotten. Return the minimum number of minutes until no fresh orange remains, or -1 if that is impossible.

Input Domain

• 1 <= rows, columns <= 100.
• Every cell is 0, 1, or 2.
• Rotting within one minute happens simultaneously.

Output Rules

• Return 0 when there are no fresh oranges initially.
• Return -1 when at least one fresh orange can never be reached.
• Return one integer, so tie semantics are not applicable.

Constraints

• Target time complexity is O(rows * columns).
• Additional space may be O(rows * columns).

Examples

Example 1

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

Output: 4

Example 2

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

Output: -1