Categories
Breadth First Search Leetcode Recursion

Oranges Rotting

let orangesRotting = function(grid) {

    const FRESH = 1,
          ROTTEN = 2,
          VISITED = -1;
    let rotten = [],
        totalFresh = 0,
        totalEmpty = 0,
        total = 0;

    function getAdjacents(row, col) {
        let result = [];
        // check top
        if (row > 0 && grid[row -1][col] === FRESH) {
            grid[row -1][col] = VISITED;
            result.push([row - 1, col]);
        }

        // check bottom
        if (row < grid.length - 1 && grid[row + 1][col] === FRESH) {
            grid[row +1][col] = VISITED;
            result.push([row + 1, col]);
        }

        // check left;
        if (col > 0 && grid[row][col - 1] === FRESH) {
            grid[row][col - 1] = VISITED;
            result.push([row, col - 1]);
        }

        // check right
        if (col < grid[row].length - 1 && grid[row][col + 1] === FRESH) {
            grid[row][col + 1] = VISITED;
            result.push([row, col + 1]);
        }

        return result;
    }

    for (let i = 0; i < grid.length; i++) {
        for (let j = 0; j < grid[i].length; j++) {
            const data = grid[i][j];
            if (data === ROTTEN) {
                rotten.push(...getAdjacents(i, j));
            }
            else if (data === FRESH || data === VISITED) {
                totalFresh++;
            }
            else {
                totalEmpty++;
            }
            total++;
        }
    }

    totalFresh -= rotten.length;
    let minute = 0;
    while (rotten.length) {
        let len = rotten.length;
        while (len --> 0) {
            let point = rotten.pop();
            let [row, col] = point;
            grid[row][col] = ROTTEN;
            rotten.unshift(...getAdjacents(row, col));
        }

        totalFresh -= rotten.length;
        minute++;
    }

    if (total === totalEmpty) return 0;

    let hasFreshOranges = totalFresh > 0;
    if (hasFreshOranges) return -1;

    return minute;
};

Leave a Reply

Your email address will not be published. Required fields are marked *