994. Rotting Oranges

Problem

Tags: Array, Breadth-First Search, Matrix

You are given an m x n grid where each cell can have one of three values:

• 0 representing an empty cell,
• 1 representing a fresh orange, or
• 2 representing a rotten orange.

Every minute, any fresh orange that is 4-directionally adjacent to a rotten orange becomes rotten.

Return the minimum number of minutes that must elapse until no cell has a fresh orange. If this is impossible, return -1.

Example 1:

Input: grid = [[2,1,1],[1,1,0],[0,1,1]]
Output: 4

Example 2:

Input: grid = [[2,1,1],[0,1,1],[1,0,1]]
Output: -1
Explanation: The orange in the bottom left corner (row 2, column 0) is never rotten, because rotting only happens 4-directionally.

Example 3:

Input: grid = [[0,2]]
Output: 0
Explanation: Since there are already no fresh oranges at minute 0, the answer is just 0.

Constraints:

• m == grid.length
• n == grid[i].length
• 1 <= m, n <= 10
• grid[i][j] is 0, 1, or 2.

Code

JS

// 994. Rotting Oranges (5/3/53733)
// Runtime: 92 ms (63.38%) Memory: 41.75 MB (94.94%) 

/**
 * @param {number[][]} grid
 * @return {number}
 */
function orangesRotting(grid) {
    const fresh = new Set();
    const rotten = [];
    for (let i = 0; i < grid.length; i++) {
        for (let j = 0; j < grid[0].length; j++) {
            if (grid[i][j] === 2) rotten.push([i, j]);
            else if (grid[i][j] === 1) fresh.add(i * 100 + j);
        }
    }

    if (rotten.length === 0) return fresh.size ? -1 : 0;

    const directions = [
        [0, 1],
        [0, -1],
        [1, 0],
        [-1, 0],
    ];
    let minutes = -1;
    while (rotten.length) {
        const num = rotten.length;
        for (let i = 0; i < num; i++) {
            const [y, x] = rotten.shift();
            for (let [dy, dx] of directions) {
                const [ny, nx] = [y + dy, x + dx];
                if (ny < 0 || ny >= grid.length || nx < 0 || nx >= grid[0].length || grid[ny][nx] !== 1) continue;
                grid[ny][nx] = 2;
                fresh.delete(ny * 100 + nx);
                rotten.push([ny, nx]);
            }
        }
        minutes++;
    }

    return fresh.size ? -1 : minutes;
}