Learning Journal

2/21/2024

Walls and Gates - Depth-First Search

Tags: algorithms leetcode graph depth_first_search

/**
 Do not return anything, modify rooms in-place instead.
 */
function wallsAndGates(rooms: number[][]): void {
    const INF = 2147483647;
   
    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)
                dfs(row, col, 0);
        }
    }


    function dfs(row:number, col:number, count: number) {
        rooms[row][col] = count;

        for(let i = 0; i < directions.length; i++) {
            const [nextR, nextC] = [row + directions[i][0], col + directions[i][1]];

            if(nextR >= 0 && nextR < numRows 
                && nextC >= 0 && nextC < numCols 
                && rooms[nextR][nextC] > count + 1){
                dfs(nextR, nextC, count + 1);
            }
        }
    }
};/**
 Do not return anything, modify rooms in-place instead.
 */
function wallsAndGates(rooms: number[][]): void {
    const INF = 2147483647;
   
    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)
                dfs(row, col, 0);
        }
    }


    function dfs(row:number, col:number, count: number) {
        rooms[row][col] = count;

        for(let i = 0; i < directions.length; i++) {
            const [nextR, nextC] = [row + directions[i][0], col + directions[i][1]];

            if(nextR >= 0 && nextR < numRows 
                && nextC >= 0 && nextC < numCols 
                && rooms[nextR][nextC] > count + 1){
                dfs(nextR, nextC, count + 1);
            }
        }
    }
};

THE PROBLEM

This is the depth-first search approach for this problem. It turns out that it's even faster than the breadth-first search approach. Why?

It is because it first travels to the end of a path before coming back to examine the next possibility. At the time it examines the next possibility, a certain number of nodes are already visited, and thus, do not needed to be checked again. Meanwhile, when doing bfs, we examine nodes levels by levels, sometimes, we need to add one node multiple times because we are not sure that a node has the smallest value until we finish the search.

Revised by ChatGPT

This is a depth-first search (DFS) approach for this problem, which is even faster than the breadth-first search (BFS) approach. The reason for its efficiency is that DFS explores as far as possible along each branch before backtracking, allowing it to reach the end of a path and mark nodes with their shortest distance from a gate. When examining the next possibility, a number of nodes are already visited and marked with their shortest distance, so they do not need to be checked again. In contrast, BFS examines nodes level by level, sometimes adding a node multiple times because it is not certain that a node has the smallest value until the search is complete. This can lead to redundant checks and slower performance compared to DFS in this context.