BFS for 01 Matrix was hard to solve without timeout using JS

245

I understand that there is a faster DP solution, but I wanted to try to solve this using BFS since that's this explore topic;

I had to re-write some function to do (nearly) the same thing but without the spread operator since it seems like that little bit of inefficiency causes it to timeout. The same algo, but different implementation was timing out which is unfortunate. Perhaps a longer timeout could be used here.

var updateMatrix = function(mat) {
    const m = mat.length;
    const n = mat[0].length;
    const result = Array.from({ length: m }, () => new Array(n).fill(Infinity));
    const q = [];
	const neighbors = (i, j) => [
		[row+1, col],
		[row-1, col],
		[row, col+1],
		[row, col-1]
	];

    for (let row = 0; row < m; ++row) {
        for (let col = 0; col < n; ++col) {
            if (mat[row][col] === 0) {
                result[row][col] = 0;
				// q.push(...neighbors(row, col)); TIMEOUT
				q.push(
                    [row+1, col],
                    [row-1, col],
                    [row, col+1],
                    [row, col-1]
                );
            }
        }
    }
    
    let depth = 1;
    let len;
    while (len = q.length) {
        for (let i = 0; i < len; ++i) {
            const [row, col] = q.shift();
            if (result[row]?.[col] > depth) {
                result[row][col] = depth;
				// q.push(...neighbors(row, col)); TIMEOUT
				q.push(
                    [row+1, col],
                    [row-1, col],
                    [row, col+1],
                    [row, col-1]
                );
            }
        }
        ++depth;
    }

    return result;
};

I used to have a function to generate the neighboring nodes q.push(...fn(node)) to push all the neignbors into the queue, but that bit right there was causing timeouts :(

Comments (1)