how to repeat same element for solving leetcode 542 by js

Question

I try to solve LeetCode 542. 01 matrix, but I get an infinite loop.

The question description:

Given an m x n binary matrix mat, return the distance of the nearest 0 for each cell.

The distance between two adjacent cells is 1.

Example 1:

Input: mat = [[0,0,0],[0,1,0],[0,0,0]]
Output: [[0,0,0],[0,1,0],[0,0,0]]

This is my code:

var updateMatrix = function (mat) {
    const m = mat.length
    const n = mat[0].length
    for (let y = 0; y < m; y++) {
        for (let x = 0; x < n; x++) {
            if (mat[y][x] !== 0) {
                mat[y][x] = Infinity
            }
        }
    }
    const bfs = (y, x, selfVal) => {
        if (y < 0 || x < 0 || y > m - 1 || x > n - 1) {
            return
        }
        if (mat[y][x] !== 0) {
            mat[y][x] = Math.min(selfVal + 1, mat[y][x])
        }
        bfs(y + 1, x, mat[y][x])
        bfs(y - 1, x, mat[y][x])
        bfs(y, x + 1, mat[y][x])
        bfs(y, x - 1, mat[y][x])
    }
    bfs(0, 0, mat[0][0])
    return mat
};

Should I add visited map to record item i visited? Or is my train of thought is entirely wrong?

Answer 1

Some issues:

• You didn't implement BFS, but DFS. A BFS algorithm typically doesn't use recursion (stack), but a queue.

• The only stop condition for your recursive search is when the coordinates are invalid. But since you will always find neighbors with valid coordinates, this recursion will just keep going, consuming the complete call stack.

• although a visited map would be a good idea, you already have a notion of visited when you update the value in the matrix. Such an update should only have to happen once for each cell, so any cell that doesn't have Infinity in it, can be considered visited.

But, you should really implement a BFS algorithm, and this should start with all "resolved" cells in the queue, i.e. the cells with the value 0. Then iterate that queue and update any neighbor that still has value Infinity (i.e. "not yet visited") to a 1. And put such updated cells in your queue. I would suggest to work with two arrays instead of one queue, so that you also can easily keep track of the distance you are currently working with.

After all has been done to update to 1, repeat the procedure with the queue that has the cell references to those updated cells. Now update "Infinity" neighbors to 2, ...etc.

Here is the updated code:

var updateMatrix = function (mat) {
    const m = mat.length;
    const n = mat[0].length;
    let bfsQueue = [];
    for (let y = 0; y < m; y++) {
        for (let x = 0; x < n; x++) {
            if (mat[y][x] !== 0) {
                mat[y][x] = Infinity;
            } else {
                bfsQueue.push([y, x]);
            }
        }
    }

    let distance = 0;
    while (bfsQueue.length) {
        const updated = [];
        distance++;
        for (const [y, x] of bfsQueue) {
            for (const [v, u] of [[y - 1, x], [y, x - 1], [y + 1, x], [y, x + 1]]) {
                if (mat[v]?.[u] == Infinity) {
                    mat[v][u] = distance;
                    updated.push([v, u]);
                }
            }
        }
        bfsQueue = updated;
    }

    return mat;
};