Learning Journal

2/21/2024

Walls and Gates - Breadth-First Search

Tags: algorithms leetcode graph breadth_first_search

/**
 Do not return anything, modify rooms in-place instead.
 */
function wallsAndGates(rooms: number[][]): void {
    const INF = 2147483647;
    const arr:([number,number]|null)[] = [];
    const numRows = rooms.length, numCols = rooms[0].length,
            up = [-1,0], down=[1,0], left=[0, -1], right=[0, 1],
            directions = [up,down,left,right];

    for(let row = 0; row < rooms.length; row++) {
        for(let col = 0; col < rooms[row].length; col++){
            if(rooms[row][col] === 0)
                arr.push([row,col]);
        }
    }

    arr.push(null);

    let count = 0, pointer = 0;

    while(pointer < arr.length - 1) {
        if(arr[pointer] === null) {
            count++;
            arr.push(null);
        }
        else {
            const [curRow, curCol] = arr[pointer];

            if(rooms[curRow][curCol] === INF)
                rooms[curRow][curCol] = count;

            for(let i = 0; i < directions.length; i++) {
                const [nextRow, nextCol] = [curRow + directions[i][0], curCol + directions[i][1]];

                if(nextRow >= 0 && nextRow < numRows && nextCol >= 0 && nextCol < numCols && rooms[nextRow][nextCol] > count){
                    arr.push([nextRow, nextCol]);
                }
            }
        }

        pointer++;
    }

};/**
 Do not return anything, modify rooms in-place instead.
 */
function wallsAndGates(rooms: number[][]): void {
    const INF = 2147483647;
    const arr:([number,number]|null)[] = [];
    const numRows = rooms.length, numCols = rooms[0].length,
            up = [-1,0], down=[1,0], left=[0, -1], right=[0, 1],
            directions = [up,down,left,right];

    for(let row = 0; row < rooms.length; row++) {
        for(let col = 0; col < rooms[row].length; col++){
            if(rooms[row][col] === 0)
                arr.push([row,col]);
        }
    }

    arr.push(null);

    let count = 0, pointer = 0;

    while(pointer < arr.length - 1) {
        if(arr[pointer] === null) {
            count++;
            arr.push(null);
        }
        else {
            const [curRow, curCol] = arr[pointer];

            if(rooms[curRow][curCol] === INF)
                rooms[curRow][curCol] = count;

            for(let i = 0; i < directions.length; i++) {
                const [nextRow, nextCol] = [curRow + directions[i][0], curCol + directions[i][1]];

                if(nextRow >= 0 && nextRow < numRows && nextCol >= 0 && nextCol < numCols && rooms[nextRow][nextCol] > count){
                    arr.push([nextRow, nextCol]);
                }
            }
        }

        pointer++;
    }

};

THE PROBLEM

This is the breadth-first search approach for this problem. First, it will add all gates to an array, then add null at the end. After that, it will use a pointer to examine each array's element, from start to end after setting a counter to 0. For each element, it will assign the current value of the counter to the cell then determine if its neighbor is an empty room. If it is, the neighbor will be added to the arr if its value is greater than the counter.

The catch here is that there will be time when the neighbor of a node is already visited and has the value less than its value + 1, if we don't take care of it, it will be added to the arr and later on, will be assigned to the greater value, which is incorrect.

Revised by ChatGPT

This is a breadth-first search approach to the problem. The algorithm starts by adding all gates to an array and appending null at the end. It then uses a pointer to iterate through each element of the array, starting with a counter set to 0. For each element, it assigns the current value of the counter to the cell and check if its neighbors are empty rooms. If a neighbor is an empty room and its value is greater than the counter, it is added to the array.

A key consideration is that a neighbor of a node may have already been visited and assigned a value less than its current value plus 1. To prevent incorrect assignments, the algorithm ensures that only neighbors with values greater than the counter are added to the array.