Practice/Amazon/Leetcode 994. Rotting Oranges

Leetcode 994. Rotting Oranges

CodingMust

Problem

You are monitoring a laboratory grid containing biological samples. Each cell in the grid can be in one of three states:

• 0: Empty cell (no sample)
• 1: Healthy sample
• 2: Infected sample

Each minute, any healthy sample that is adjacent (up, down, left, right — not diagonally) to an infected sample becomes infected. The infection spreads continuously in this manner.

Your task is to determine the minimum number of minutes that must elapse until there are no more healthy samples remaining in the grid. If it's impossible for all healthy samples to become infected, return -1.

Requirements

1. Calculate the minimum time for all healthy samples to become infected
2. Return -1 if any healthy sample cannot be reached by the spreading infection
3. Handle multiple initial infection sources simultaneously
4. Consider only 4-directional adjacency (not diagonal)

Constraints

• 1 ≤ m, n ≤ 10 (grid dimensions)
• grid[i][j] is 0, 1, or 2
• Time complexity should be O(m × n)
• Space complexity should be O(m × n)

Examples

Example 1:

Input: grid = [[2,1,1],[1,1,0],[0,1,1]] Output: 4 Explanation: Minute 0: Infected samples at (0,0) Minute 1: Infection spreads to (0,1) and (1,0) Minute 2: Infection spreads to (0,2) and (1,1) Minute 3: Infection spreads to (2,1) Minute 4: Infection spreads to (2,2) All samples are now infected.

Example 2:

Input: grid = [[2,1,1],[0,0,0],[1,1,1]] Output: -1 Explanation: The healthy samples in the bottom row are isolated by empty cells. The infection cannot cross empty cells, so these samples remain healthy forever.

Example 3:

Input: grid = [[2,2],[2,2]] Output: 0 Explanation: All samples are already infected at the start, so 0 minutes are required.