Rotting Oranges (Infection Spread)

Given a 2D array where each cell can have one of three values:

0 represents an empty cell
1 represents a healthy person
2 represents a sick person

Each minute that passes, any healthy person who is adjacent to a sick person becomes sick. Return the total number of minutes that must elapse until every person is sick.

Note: If it is not possible for each person to become sick, return -1.

Example(s)

Example 1:

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

Output: 4
Explanation:
Minute 0: Initial state
  [1,1,1]
  [1,1,0]
  [0,1,2]  (sick person at [2,2])

Minute 1: [2,1] becomes sick
  [1,1,1]
  [1,1,0]
  [0,2,2]

Minute 2: [1,1] becomes sick
  [1,2,1]
  [1,1,0]
  [0,2,2]

Minute 3: [1,0] and [0,1] become sick
  [2,2,1]
  [2,1,0]
  [0,2,2]

Minute 4: [0,0] and [0,2] become sick
  [2,2,2]
  [2,2,0]
  [0,2,2]

All healthy people are now sick (or empty cells remain).

Example 2:

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

Output: -1
Explanation:
The healthy person at [0,2] cannot be reached by any sick person
due to the barrier of empty cells [0,0,0] in the middle row.

Example 3:

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

Output: 4
Explanation:
Similar to Example 1, but starts with sick person at [0,0].

Solution

The solution uses BFS (Breadth-First Search):

Find all sick people: Collect all positions with value 2
BFS from all sick people: Use multi-source BFS to spread infection
Track minutes: Each BFS level represents one minute
Count healthy people: Track how many healthy people remain
Check completion: If healthy count > 0 after BFS, return -1

JavaScript Solution
Python Solution

JavaScript Solution - BFS

/**
* Find minutes until all people are sick
* @param {number[][]} grid - 2D array (0=empty, 1=healthy, 2=sick)
* @return {number} - Minutes until all sick, or -1 if impossible
*/
function orangesRotting(grid) {
if (!grid || grid.length === 0) return 0;

const rows = grid.length;
const cols = grid[0].length;
const queue = [];
let healthyCount = 0;

// Step 1: Find all sick people and count healthy people
for (let i = 0; i < rows; i++) {
  for (let j = 0; j < cols; j++) {
    if (grid[i][j] === 2) {
      queue.push([i, j, 0]); // [row, col, minute]
    } else if (grid[i][j] === 1) {
      healthyCount++;
    }
  }
}

// If no healthy people, return 0
if (healthyCount === 0) return 0;

// Step 2: BFS to spread infection
const directions = [[-1, 0], [1, 0], [0, -1], [0, 1]]; // up, down, left, right
let minutes = 0;

while (queue.length > 0) {
  const [row, col, time] = queue.shift();
  minutes = time;
  
  // Check all 4 directions
  for (const [dr, dc] of directions) {
    const newRow = row + dr;
    const newCol = col + dc;
    
    // Check bounds and if cell is healthy
    if (
      newRow >= 0 && newRow < rows &&
      newCol >= 0 && newCol < cols &&
      grid[newRow][newCol] === 1
    ) {
      // Make this person sick
      grid[newRow][newCol] = 2;
      healthyCount--;
      queue.push([newRow, newCol, time + 1]);
    }
  }
}

// If healthy people remain, return -1
return healthyCount === 0 ? minutes : -1;
}

// Test cases
const grid1 = [
[1,1,1],
[1,1,0],
[0,1,2]
];
console.log('Example 1:', orangesRotting(grid1)); // 4

const grid2 = [
[1,1,1],
[0,0,0],
[2,0,1]
];
console.log('Example 2:', orangesRotting(grid2)); // -1

const grid3 = [
[2,1,1],
[1,1,0],
[0,1,1]
];
console.log('Example 3:', orangesRotting(grid3)); // 4

const grid4 = [
[2,2],
[1,1],
[0,0],
[2,0]
];
console.log('Test 4:', orangesRotting(grid4)); // 2

Output:

Click "Run Code" to execute the code and see the results.

Python Solution - BFS

from typing import List
from collections import deque

def oranges_rotting(grid: List[List[int]]) -> int:
  """
  Find minutes until all people are sick
  
  Args:
      grid: 2D array (0=empty, 1=healthy, 2=sick)
      
  Returns:
      int: Minutes until all sick, or -1 if impossible
  """
  if not grid or not grid[0]:
      return 0
  
  rows = len(grid)
  cols = len(grid[0])
  queue = deque()
  healthy_count = 0
  
  # Step 1: Find all sick people and count healthy people
  for i in range(rows):
      for j in range(cols):
          if grid[i][j] == 2:
              queue.append((i, j, 0))  # (row, col, minute)
          elif grid[i][j] == 1:
              healthy_count += 1
  
  # If no healthy people, return 0
  if healthy_count == 0:
      return 0
  
  # Step 2: BFS to spread infection
  directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]  # up, down, left, right
  minutes = 0
  
  while queue:
      row, col, time = queue.popleft()
      minutes = time
      
      # Check all 4 directions
      for dr, dc in directions:
          new_row = row + dr
          new_col = col + dc
          
          # Check bounds and if cell is healthy
          if (
              0 <= new_row < rows and
              0 <= new_col < cols and
              grid[new_row][new_col] == 1
          ):
              # Make this person sick
              grid[new_row][new_col] = 2
              healthy_count -= 1
              queue.append((new_row, new_col, time + 1))
  
  # If healthy people remain, return -1
  return minutes if healthy_count == 0 else -1

# Test cases
grid1 = [
  [1,1,1],
  [1,1,0],
  [0,1,2]
]
print('Example 1:', oranges_rotting(grid1))  # 4

grid2 = [
  [1,1,1],
  [0,0,0],
  [2,0,1]
]
print('Example 2:', oranges_rotting(grid2))  # -1

grid3 = [
  [2,1,1],
  [1,1,0],
  [0,1,1]
]
print('Example 3:', oranges_rotting(grid3))  # 4

grid4 = [
  [2,2],
  [1,1],
  [0,0],
  [2,0]
]
print('Test 4:', oranges_rotting(grid4))  # 2

Loading Python runtime...

Output:

Click "Run Code" to execute the code and see the results.

Alternative Solution (Level-by-Level BFS)

Here's a version that processes level by level more explicitly:

JavaScript Level-by-Level
Python Level-by-Level

/**
 * Alternative: Level-by-level BFS
 */
function orangesRottingLevelByLevel(grid) {
  if (!grid || grid.length === 0) return 0;
  
  const rows = grid.length;
  const cols = grid[0].length;
  const queue = [];
  let healthyCount = 0;
  
  // Find all sick people and count healthy
  for (let i = 0; i < rows; i++) {
    for (let j = 0; j < cols; j++) {
      if (grid[i][j] === 2) {
        queue.push([i, j]);
      } else if (grid[i][j] === 1) {
        healthyCount++;
      }
    }
  }
  
  if (healthyCount === 0) return 0;
  
  const directions = [[-1,0], [1,0], [0,-1], [0,1]];
  let minutes = 0;
  
  // Process level by level
  while (queue.length > 0) {
    const size = queue.length;
    let infectedThisMinute = false;
    
    // Process all nodes at current level
    for (let i = 0; i < size; i++) {
      const [row, col] = queue.shift();
      
      for (const [dr, dc] of directions) {
        const newRow = row + dr;
        const newCol = col + dc;
        
        if (
          newRow >= 0 && newRow < rows &&
          newCol >= 0 && newCol < cols &&
          grid[newRow][newCol] === 1
        ) {
          grid[newRow][newCol] = 2;
          healthyCount--;
          queue.push([newRow, newCol]);
          infectedThisMinute = true;
        }
      }
    }
    
    if (infectedThisMinute) {
      minutes++;
    }
  }
  
  return healthyCount === 0 ? minutes : -1;
}

def oranges_rotting_level_by_level(grid: List[List[int]]) -> int:
    """
    Alternative: Level-by-level BFS
    """
    if not grid or not grid[0]:
        return 0
    
    rows = len(grid)
    cols = len(grid[0])
    queue = deque()
    healthy_count = 0
    
    # Find all sick people and count healthy
    for i in range(rows):
        for j in range(cols):
            if grid[i][j] == 2:
                queue.append((i, j))
            elif grid[i][j] == 1:
                healthy_count += 1
    
    if healthy_count == 0:
        return 0
    
    directions = [(-1,0), (1,0), (0,-1), (0,1)]
    minutes = 0
    
    # Process level by level
    while queue:
        size = len(queue)
        infected_this_minute = False
        
        # Process all nodes at current level
        for _ in range(size):
            row, col = queue.popleft()
            
            for dr, dc in directions:
                new_row = row + dr
                new_col = col + dc
                
                if (
                    0 <= new_row < rows and
                    0 <= new_col < cols and
                    grid[new_row][new_col] == 1
                ):
                    grid[new_row][new_col] = 2
                    healthy_count -= 1
                    queue.append((new_row, new_col))
                    infected_this_minute = True
        
        if infected_this_minute:
            minutes += 1
    
    return minutes if healthy_count == 0 else -1

Complexity

Time Complexity: O(m × n) - Where m and n are the dimensions of the grid. We visit each cell at most once.
Space Complexity: O(m × n) - For the BFS queue. In the worst case, all cells might be in the queue.

Approach

The solution uses multi-source BFS:

Initial scan:
- Find all sick people (value 2) and add them to queue
- Count healthy people (value 1)
BFS propagation:
- Process all sick people at current minute
- For each sick person, check 4 adjacent cells
- If adjacent cell is healthy, make it sick and add to queue
Track minutes:
- Each BFS level represents one minute
- Update minutes as we process each level
Check completion:
- After BFS completes, check if healthyCount is 0
- If healthyCount > 0, return -1 (impossible)
- Otherwise, return minutes

Key Insights

Multi-source BFS: Start BFS from all sick people simultaneously
Level-by-level: Each BFS level = 1 minute
Track healthy count: Need to verify all healthy people became sick
4-directional: Check up, down, left, right (not diagonals)
In-place modification: Mark cells as sick (2) as we process them

Step-by-Step Example

Let's trace through Example 1: grid = [[1,1,1],[1,1,0],[0,1,2]]

Initial state:
  [1,1,1]
  [1,1,0]
  [0,1,2]
  
  Queue: [(2,2,0)]
  healthyCount = 6

Minute 0 → 1:
  Process (2,2):
    Check (1,2): grid[1][2] = 0 (empty, skip)
    Check (3,2): out of bounds
    Check (2,1): grid[2][1] = 1 (healthy) → make sick
      Queue: [(2,1,1)]
      healthyCount = 5
    Check (2,3): out of bounds
  
  State:
    [1,1,1]
    [1,1,0]
    [0,2,2]

Minute 1 → 2:
  Process (2,1):
    Check (1,1): grid[1][1] = 1 → make sick
      Queue: [(1,1,2)]
      healthyCount = 4
    Check (3,1): out of bounds
    Check (2,0): grid[2][0] = 0 (empty, skip)
    Check (2,2): already sick
  
  State:
    [1,1,1]
    [1,2,0]
    [0,2,2]

Minute 2 → 3:
  Process (1,1):
    Check (0,1): grid[0][1] = 1 → make sick
      Queue: [(0,1,3)]
      healthyCount = 3
    Check (2,1): already sick
    Check (1,0): grid[1][0] = 1 → make sick
      Queue: [(1,0,3)]
      healthyCount = 2
    Check (1,2): grid[1][2] = 0 (empty, skip)
  
  State:
    [1,2,1]
    [2,2,0]
    [0,2,2]

Minute 3 → 4:
  Process (0,1):
    Check (-1,1): out of bounds
    Check (1,1): already sick
    Check (0,0): grid[0][0] = 1 → make sick
      Queue: [(0,0,4)]
      healthyCount = 1
    Check (0,2): grid[0][2] = 1 → make sick
      Queue: [(0,2,4)]
      healthyCount = 0
  
  Process (1,0):
    Already processed, skip
  
  State:
    [2,2,2]
    [2,2,0]
    [0,2,2]

Minute 4:
  Process (0,0) and (0,2):
    No new healthy people to infect
  
  Final: healthyCount = 0, minutes = 4
  Return: 4

Visual Representation

Initial:        Minute 1:      Minute 2:      Minute 3:      Minute 4:
[1,1,1]        [1,1,1]        [1,2,1]        [2,2,1]        [2,2,2]
[1,1,0]   →    [1,1,0]   →    [1,2,0]   →    [2,2,0]   →    [2,2,0]
[0,1,2]        [0,2,2]        [0,2,2]        [0,2,2]        [0,2,2]
                ↑              ↑              ↑              ↑
              infected       infected       infected       all done

Edge Cases

No healthy people: Return 0 (already all sick)
No sick people: Return -1 (can't spread)
All empty cells: Return 0
Isolated healthy people: Return -1 (barrier prevents infection)
Multiple sick sources: BFS handles multiple starting points

Important Notes

Multi-source BFS: All sick people start spreading simultaneously
4-directional: Only adjacent cells (up, down, left, right)
Empty cells (0): Act as barriers, cannot be infected
In-place modification: Mark cells as 2 as we process them
Healthy count tracking: Must verify all healthy people became sick

Walls and Gates: Similar BFS problem
Number of Islands: Different but uses BFS
01 Matrix: Distance from nearest 0
Shortest Path in Binary Matrix: BFS pathfinding

Takeaways

Multi-source BFS handles multiple starting points efficiently
Level-by-level processing naturally represents time progression
Track healthy count to verify completion
4-directional check is standard for grid problems
O(m×n) time is optimal (must visit all cells)

Example(s)​

Solution​

JavaScript Solution - BFS

Output:

Python Solution - BFS

Output:

Alternative Solution (Level-by-Level BFS)​

Complexity​

Approach​

Key Insights​

Step-by-Step Example​

Visual Representation​

Edge Cases​

Important Notes​

Related Problems​

Takeaways​

Example(s)

Solution

Alternative Solution (Level-by-Level BFS)

Complexity

Approach

Key Insights

Step-by-Step Example

Visual Representation

Edge Cases

Important Notes

Related Problems

Takeaways