Saltar al contenido principal

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):

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

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.

Alternative Solution (Level-by-Level BFS)​

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

/**
 * 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;
}

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:

  1. Initial scan:

    • Find all sick people (value 2) and add them to queue
    • Count healthy people (value 1)

  2. 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

  3. Track minutes:

    • Each BFS level represents one minute
    • Update minutes as we process each level

  4. 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)