Question 54200 in Javascript Question posted in
A very good W3school tutorial can be found here.

how to repeat same element for solving leetcode 542 by js – Javascript

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?

Tags:

2

Answers


  1. 0

    You definitely need a visited array. Without one, you’ll run into the issue where two adjacent 1s will just bfs back and forth into one another. You need to make sure that once you bfs from a cell, you never bfs from it again; this works because you know you’ll never reach this cell with a lower distance than the first time you bfs’d into it.

    Best of luck!

    Login or Signup to reply.
  2. 0

    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;
};
    Login or Signup to reply.
Please signup or login to give your own answer.

Back To Top
Search