Learning Journal

2/14/2024

Rotting Oranges - 2nd attempt

Tags: algorithms leetcode graph breadth_first_search

function orangesRotting(grid: number[][]): number {
    const rottedCoord:[number,number][] = [];
    let freshOranges = 0;

    for(let row = 0; row < grid.length; row++) {
        for(let col = 0; col < grid[row].length; col++) {
            if(grid[row][col] === 1){
                freshOranges++;
            }
            else if(grid[row][col] === 2){
                rottedCoord.push([row,col]);
            }
        }
    }

    let time = 0, pointer = 0;

    rottedCoord.push([-1,-1]);

    while(pointer < rottedCoord.length) {
        if(rottedCoord[pointer][0] === -1) {
            if(pointer === rottedCoord.length - 1)
                break;
            else {
                rottedCoord.push([-1,-1]);
                pointer++;
                time++;
           }
        }
        else {
            const curRot = rottedCoord[pointer];

            const left = [0,-1], right = [0,1], up =[-1,0], down =[1, 0],
                directions = [up, down, left, right];
            
            for(let i = 0; i < directions.length; i++) {
                const nextR = curRot[0] + directions[i][0];
                const nextC = curRot[1] + directions[i][1];

                if(nextR >=0 && nextR < grid.length 
                    && nextC >= 0 && nextC < grid[nextR].length 
                    && grid[nextR][nextC] === 1) {
                        grid[nextR][nextC] = 2;
                        
                        freshOranges--;

                        rottedCoord.push([nextR, nextC]);

                }
            }
            pointer++;
        }
    }


    if(freshOranges === 0)
        return time;
    
    return -1;

   
};  Qfunction orangesRotting(grid: number[][]): number {
    const rottedCoord:[number,number][] = [];
    let freshOranges = 0;

    for(let row = 0; row < grid.length; row++) {
        for(let col = 0; col < grid[row].length; col++) {
            if(grid[row][col] === 1){
                freshOranges++;
            }
            else if(grid[row][col] === 2){
                rottedCoord.push([row,col]);
            }
        }
    }

    let time = 0, pointer = 0;

    rottedCoord.push([-1,-1]);

    while(pointer < rottedCoord.length) {
        if(rottedCoord[pointer][0] === -1) {
            if(pointer === rottedCoord.length - 1)
                break;
            else {
                rottedCoord.push([-1,-1]);
                pointer++;
                time++;
           }
        }
        else {
            const curRot = rottedCoord[pointer];

            const left = [0,-1], right = [0,1], up =[-1,0], down =[1, 0],
                directions = [up, down, left, right];
            
            for(let i = 0; i < directions.length; i++) {
                const nextR = curRot[0] + directions[i][0];
                const nextC = curRot[1] + directions[i][1];

                if(nextR >=0 && nextR < grid.length 
                    && nextC >= 0 && nextC < grid[nextR].length 
                    && grid[nextR][nextC] === 1) {
                        grid[nextR][nextC] = 2;
                        
                        freshOranges--;

                        rottedCoord.push([nextR, nextC]);

                }
            }
            pointer++;
        }
    }


    if(freshOranges === 0)
        return time;
    
    return -1;

   
};  Q

THE PROBLEM

Essentially, this problem is about finding the shortest path from the original rotted oranges to all the fresh oranges they are connected to. To find the shortest path, we can employ the breadth-first-search algorithm in the graph.

First, we need to collect all the information of the graph: the number of fresh oranges (later on, when each fresh orange turns rotted, we just decrease this number by 1, and at the end, if there are still some fresh oranges left, we just return -1, signify that we cannot rot all of the fresh orange; the coordinate of the rotted oranges. Because we do the breadth first search, we need to use the queue. Here, I use the array to push new element in and use a pointer traverse through the array from element 0 to "dequeue" the element.

The key aspect of this solution is we need to keep track of the time. But, if we put all of the rotted oranges to an array, how can we know when does one round finish? Well, we just mark it with a special node [-1,-1].

Revised by ChatGPT

This problem is a classic example of using the breadth-first-search (BFS) algorithm to find the minimum time required to spread a condition across a grid. In this case, the condition is the rotting of oranges.

The key steps in solving this problem are as follows:

Initialization: Start by counting the number of fresh oranges and identifying the positions of the rotted oranges. Thes positions will serve as the starting points to our BFS.
BFS Implementation: Use a queue to perform the BFS. Each element in queue represents a rotted orange, and we process these elements in a FIFO (first-in, first-out) manner. To keep track of time, we insert a special marker ([-1,-1]) at the end of each round of BFS. This marker signifies the completion of one time unit.
Rotting Process: For each rotted orange, we check its four adjacent cells (up,down, left, right). If any of these cells contain a fresh orange, we rot it (change its value from 1 to 2) and add its position to the queue. This process continues until the queue is empty.
Time Calculation: The number of rounds in the BFS, indicated by the number of special markers encountered, gives us the total time required to rot all reachable fresh oranges.
Final Check: If there are still fresh oranges remaining (i.e., they are unreachable from the initially rotted oranges), we return -1. Otherwise, we return the total time.

By using BFS, we ensure that we are always processing oranges in the order they are infected, which guarantees that we find the minimum time required to rot all reachable oranges.