0994-rotting-oranges.js

/**
 * https://leetcode.com/problems/rotting-oranges/
 * Time O(ROWS * COLS) | Space O(ROWS * COLS)
 * @param {number[][]} grid
 * @return {number}
 */
var orangesRotting = function(grid) {
    const { queue, orangeCount } = searchGrid(grid);  /* Time O(ROWS * COLS) */
    const { rottenCount, minutes } = bfs(grid, queue);

    const isEqual = orangeCount === rottenCount;
    return isEqual
        ? minutes
        : -1;
};

const searchGrid = (grid, orangeCount = 0, queue = new Queue([])) => {
    const [ rows, cols ] = [ grid.length, grid[0].length ];

    for (let row = 0; row < rows; row++){/* Time O(ROWS) */
        for (let col = 0; col < cols; col++) {/* Time O(COLS) */
            const isEmpty = grid[row][col] === 0;
            if (!isEmpty) orangeCount++;

            const isRotten = grid[row][col] === 2;
            if (isRotten) queue.enqueue([ row, col ]);/* Space O(ROWS * COLS) */
        }
    }

    return { queue, orangeCount }
}

const bfs = (grid, queue, rottenCount = 0, minutes = 0) => {
    while (!queue.isEmpty()) {
        rottenCount += queue.size();

        for (let i = (queue.size() - 1); 0 <= i; i--) {/* Time O(WIDTH) */
            expireFresh(grid, queue);
        }

        if (queue.size()) minutes++;
    }

    return { rottenCount, minutes };
}

var expireFresh = (grid, queue) => {
    const [ rows, cols ] = [ grid.length, grid[0].length ];
    const [ row, col ] = queue.dequeue();

    for (const [ _row, _col ] of getNeighbors(row, rows, col, cols)) {
        const isFresh = grid[_row][_col] === 1;
        if (!isFresh) continue;

        grid[_row][_col] = 2;
        queue.enqueue([ _row, _col ]);/* Space O(ROWS * COLS) */
    }
}

var getNeighbors = (row, rows, col, cols) => [ [ 0, 1 ],[ 0, -1 ], [ 1, 0 ], [ -1, 0 ] ]
    .map(([ _row, _col ]) => [ (row + _row), (col + _col) ])
    .filter(([ _row, _col ]) => (0 <= _row) && (_row < rows) && (0 <= _col) && (_col < cols));

/**
 * https://leetcode.com/problems/rotting-oranges/
 * Time O((ROWS * COLS)^2) | Space O(1)
 * @param {number[][]} grid
 * @return {number}
 */
var orangesRotting = function(grid, minutes = 2) {
    while (expireFresh(grid, minutes)) minutes++;/* Time O((ROWS * COLS)^2) */

    return !hasFresh(grid)                       /* Time O(ROWS * COLS) */
        ? (minutes - 2)
        : -1;
}

var expireFresh = (grid, minutes, toBeContinued = false) => {
    const [ rows, cols ] = [ grid.length, grid[0].length ];

    for (let row = 0; row < rows; row++) {/* Time O(ROWS) */
        for (let col = 0; col < cols; col++) {/* Time O(COLS) */
            const isEqual = grid[row][col] === minutes;
            if (!isEqual) continue;

            for (const [ _row, _col ] of getNeighbors(row, rows, col, cols)) {
                const isFresh = grid[_row][_col] === 1;
                if (!isFresh) continue;

                grid[_row][_col] = (minutes + 1);
                toBeContinued = true;
            }
        }
    }

    return toBeContinued;
}

var getNeighbors = (row, rows, col, cols) => [ [ 0, 1 ],[ 0, -1 ], [ 1, 0 ], [ -1, 0 ] ]
    .map(([ _row, _col ]) => [ (row + _row), (col + _col) ])
    .filter(([ _row, _col ]) => (0 <= _row) && (_row < rows) && (0 <= _col) && (_col < cols));

const hasFresh = (grid) => {
    for (const row of grid) {/* Time O(ROWS) */
        for (const cell of row) {/* Time O(COLS) */
            const isFresh = cell === 1;
            if (isFresh) return true;
        }
    }

    return false;
}