Learning Journal

2/15/2024

Rotting Oranges - 3rd attempt

Tags: algorithms leetcode breadth_first_search

function orangesRotting(grid: number[][]): number {
    let time = -1, pointer = 0, freshOranges = 0;
    const queue: [number,number][] = [];
    
    for(let row = 0; row < grid.length; row++) {
        for(let col = 0; col < grid[row].length; col++){
            if(grid[row][col] === 2)
                queue.push([row,col]);
            else if(grid[row][col] === 1)
                freshOranges++;
        }
    }

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

    while(pointer < queue.length) {
        const curOrg = queue[pointer];

        if(curOrg[0] !== -1) {
            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 nRow = curOrg[0] + directions[i][0];
                const nCol = curOrg[1] + directions[i][1];

                if(nRow >= 0 && nRow < grid.length 
                    && nCol >= 0 && nCol < grid[nRow].length 
                    && grid[nRow][nCol] === 1) {
                    grid[nRow][nCol] = 2;
                    queue.push([nRow, nCol]);
                    freshOranges--;
                }
            }
        }
        else {
            time++;
            if(pointer !== queue.length - 1) {
                queue.push([-1,-1]);
            }
        }

        pointer++;
    }

    if(freshOranges === 0) return time;

    return -1;
   
};  function orangesRotting(grid: number[][]): number {
    let time = -1, pointer = 0, freshOranges = 0;
    const queue: [number,number][] = [];
    
    for(let row = 0; row < grid.length; row++) {
        for(let col = 0; col < grid[row].length; col++){
            if(grid[row][col] === 2)
                queue.push([row,col]);
            else if(grid[row][col] === 1)
                freshOranges++;
        }
    }

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

    while(pointer < queue.length) {
        const curOrg = queue[pointer];

        if(curOrg[0] !== -1) {
            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 nRow = curOrg[0] + directions[i][0];
                const nCol = curOrg[1] + directions[i][1];

                if(nRow >= 0 && nRow < grid.length 
                    && nCol >= 0 && nCol < grid[nRow].length 
                    && grid[nRow][nCol] === 1) {
                    grid[nRow][nCol] = 2;
                    queue.push([nRow, nCol]);
                    freshOranges--;
                }
            }
        }
        else {
            time++;
            if(pointer !== queue.length - 1) {
                queue.push([-1,-1]);
            }
        }

        pointer++;
    }

    if(freshOranges === 0) return time;

    return -1;
   
};  

THE PROBLEM

Essentially, this problem is finding the shortest path to all reachable vertices from a number of given vertices in a directed graph. The vertices are oranges, the given vertices are the rotted one at the beginning, the edge is formed between all the neighboring oranges, the direction is from either rotted to fresh or fresh to fresh. There are two catches. First, you need to count the steps of the shortest path and, second, you need to know whether or not you can reach all the vertices given the vertices at the beginning. To find the shortest path in a directed graph, we can use a queue to perform breadth first search algorithm. Basically, in each round, you take vertices from the queue, one by one, find its neighbor vetices, push those that is a fresh orange (because the direction only goes from rotted to fresh, not rotted to rotted). After each round, you increase the timer by one. You keep doing that until you run out of vertices to push to the queue. Then you return the timer. However, how do you know that you reaches all of the fresh oranges to return the timer? (Otherwise, you need to return -1 indicating that you can not reach all of the fresh oranges). The simple solution is that you can iterate the grid at the beginning to get how many fresh oranges there are (you need to do that anyway to add all of the rotten oranges originally to the queue). Then, after each time you see a fresh orange on your breadth first search way, you just decrease the number of fresh oranges by one. At the end, you can check whether or not that number goes to 0.

Revised by ChatGPT

This problem essentially involves finding the shortest path to all reachable vertices in a directed graph, where vertices represent oranges, and edges exist between neighboring oranges. The initial vertices are the rotten oranges and the direction of traversal is from rotten to fresh or from fresh to fresh.

There are two main challenges: counting the steps in the shortest path and determining whether all vertices (oranges) can be reached from the initial set of vertices (rotten oranges). To solve this, we can use a queue to implement a breath-first search (BFS) algorithm. In each round of BFS, we dequeue vertices one by one, find their neighboring vertices, and enqueue those that are fresh oranges. After each round, we increment a timer to count the steps. This process continues until the queue is empty.

To determine whether all fresh oranges have been reached, we initially count the number of fresh oranges in the grid. Each time we encounter a fresh orange during the BFS, we decrement this count. If, at the end of the BFS, the count of fresh oranges is zero, it means all fresh oranges have been reached, and we return the timer value. Otherwise, we return -1 to indicate that not all fresh oranges could be reached.

This approach ensures that we find the shortest path to all reachable fresh oranges while also verifying that all fresh oranges have been infected.