Rotting Oranges medium

Problem Statement

You are given an m x n grid representing a matrix where each cell contains a positive integer denoting the number of oranges. When two oranges are adjacent (horizontally or vertically), we can consider them to be part of the same group. Each minute, every orange that is rotting will spread the rot to its adjacent fresh oranges.

Return the minimum number of minutes that must elapse until all oranges have become rotten. If this is impossible, return -1.

Example 1

Input: grid = [[2,1,1],[1,1,0],[0,1,1]] Output: 4 Explanation: The rotting oranges are initially in the positions (0,0), (0,1), and (1,1). The process will occur as follows:

• Minute 1: The orange at (0,0) rots the oranges at (0,1), (1,0).
• Minute 2: The orange at (0,1) rots the orange at (1,1), and the orange at (1,0) rots the orange at (1,1).
• Minute 3: The orange at (1,1) rots the orange at (1,2).
• Minute 4: The orange at (1,2) rots the orange at (2,2). At this point, there are no fresh oranges remaining.

Example 2

Input: grid = [[2,1,1],[0,1,1],[1,0,1]] Output: -1 Explanation: The orange at (0, 2) will never rot because it is not adjacent to any rotting oranges.

Steps

1. Initialization:

   • Find all initial rotting oranges and add their coordinates to a queue.
   • Count the total number of fresh oranges.

2. BFS (Breadth-First Search):

   • While the queue is not empty:
     • Dequeue an orange's coordinates.
     • For each adjacent cell:
       • If it's a fresh orange:
         • Mark it as rotten.
         • Enqueue its coordinates.
         • Decrement the count of fresh oranges.

3. Result:

   • If the count of fresh oranges is 0, return the number of minutes (iterations).
   • Otherwise, return -1 (impossible to rot all oranges).

Explanation

The problem can be efficiently solved using Breadth-First Search (BFS). BFS guarantees that we explore oranges in the order they get rotten. By keeping track of the number of fresh oranges and decrementing the count as they rot, we can determine if it's possible to rot all oranges and find the minimum time required.

Code

function orangesRotting(grid: number[][]): number {
    const rows = grid.length;
    const cols = grid[0].length;
    let freshOranges = 0;
    const queue: [number, number][] = []; // Queue for BFS

    // Find initial rotting oranges and count fresh oranges
    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) {
                freshOranges++;
            }
        }
    }

    // BFS to simulate rotting process
    let minutes = 0;
    const directions = [[0, 1], [0, -1], [1, 0], [-1, 0]]; // Right, Left, Down, Up
    while (queue.length > 0) {
        const size = queue.length;
        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;
                    queue.push([newRow, newCol]);
                    freshOranges--;
                }
            }
        }
        minutes++;
    }

    // Check if all oranges are rotten
    return freshOranges === 0 ? minutes - (minutes === 0 ? 0 : 1) : -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) in the worst case, when all oranges are initially rotting, the queue could store all the cells in the grid.