Learning Journal

2/21/2024

Pacific Atlantic Water Flow - Depth-First Search

Tags: algorithms leetcode depth_first_search

function pacificAtlantic(heights: number[][]): number[][] {
    const NUM_ROWS = heights.length, NUM_COLS = heights[0].length;

    const up = [-1,0], down = [1,0], left = [0, -1], right = [0, 1],
          DIRECTIONS = [up,down,left,right];



    const reachablePacific:boolean[][] = Array(NUM_ROWS).fill(0).map((_,i) => {
        if(i === 0) return Array(NUM_COLS).fill(true);

        return Array(NUM_COLS).fill(false);
    });

    const reachableAtlantic:boolean[][] = Array(NUM_ROWS).fill(0).map((_,i) => {
        if(i === NUM_ROWS -1) return Array(NUM_COLS).fill(true);

        return Array(NUM_COLS).fill(false);
    });

    
    for(let col = 0; col < NUM_COLS; col++) {
        scan(reachablePacific, 0, col);
        scan(reachableAtlantic, NUM_ROWS -1, col);
    }

    for(let row = 1; row < NUM_ROWS; row++){
        scan(reachablePacific,row,0);
        scan(reachableAtlantic,NUM_ROWS - 1 - row, NUM_COLS - 1);
    }
    


    const result:number[][] = [];

    for(let row = 0; row < NUM_ROWS; row++){
        for(let col = 0; col < NUM_COLS; col++) {
            if(reachablePacific[row][col] && reachableAtlantic[row][col]){
                result.push([row,col]);
            }
        }
    }

    return result;


    function scan(reachable:boolean[][], row: number, col:number) {
        reachable[row][col] = true;

        for(let i = 0; i < DIRECTIONS.length; i++) {
            const nextRow = row + DIRECTIONS[i][0];
            const nextCol = col + DIRECTIONS[i][1];

            if(nextRow >= 0 && nextRow < NUM_ROWS 
                && nextCol >= 0 && nextCol < NUM_COLS
                && !reachable[nextRow][nextCol] 
                && heights[nextRow][nextCol] >= heights[row][col]){
                scan(reachable, nextRow, nextCol);
            }
        }
    }
};

function pacificAtlantic(heights: number[][]): number[][] {
    const NUM_ROWS = heights.length, NUM_COLS = heights[0].length;

    const up = [-1,0], down = [1,0], left = [0, -1], right = [0, 1],
          DIRECTIONS = [up,down,left,right];



    const reachablePacific:boolean[][] = Array(NUM_ROWS).fill(0).map((_,i) => {
        if(i === 0) return Array(NUM_COLS).fill(true);

        return Array(NUM_COLS).fill(false);
    });

    const reachableAtlantic:boolean[][] = Array(NUM_ROWS).fill(0).map((_,i) => {
        if(i === NUM_ROWS -1) return Array(NUM_COLS).fill(true);

        return Array(NUM_COLS).fill(false);
    });

    
    for(let col = 0; col < NUM_COLS; col++) {
        scan(reachablePacific, 0, col);
        scan(reachableAtlantic, NUM_ROWS -1, col);
    }

    for(let row = 1; row < NUM_ROWS; row++){
        scan(reachablePacific,row,0);
        scan(reachableAtlantic,NUM_ROWS - 1 - row, NUM_COLS - 1);
    }
    


    const result:number[][] = [];

    for(let row = 0; row < NUM_ROWS; row++){
        for(let col = 0; col < NUM_COLS; col++) {
            if(reachablePacific[row][col] && reachableAtlantic[row][col]){
                result.push([row,col]);
            }
        }
    }

    return result;


    function scan(reachable:boolean[][], row: number, col:number) {
        reachable[row][col] = true;

        for(let i = 0; i < DIRECTIONS.length; i++) {
            const nextRow = row + DIRECTIONS[i][0];
            const nextCol = col + DIRECTIONS[i][1];

            if(nextRow >= 0 && nextRow < NUM_ROWS 
                && nextCol >= 0 && nextCol < NUM_COLS
                && !reachable[nextRow][nextCol] 
                && heights[nextRow][nextCol] >= heights[row][col]){
                scan(reachable, nextRow, nextCol);
            }
        }
    }
};

THE PROBLEM

This is the depth-first search approach to the problem. Instead of adding all valid nodes to a queue then pop them out one by one in FIFO order while adding back all the nodes connected to it to the queue like in the breadth-first search, we can use a for loop to examine each valid node, one by one, to go furthest that we can reach for each node, then go back and check another node.

To go furthest, we can use recursive function, in which if we find some neighbor that is valid, we call the recursive function immediately, before checking other neighbor.

Revised by ChatGPT

This is the depth-first search (DFS) approach to the problem. Unlike the breadth-first search (BFS) approach, where we add all valid nodes to a queue and then pop them out one by one in FIFO order while adding back all the connected nodes to the queue, in DFS, we use a for loop to examine each valid node one by one and go as far as we can reach for each node before backtracking to check another node.

To go as far as possible, we use a recursive function. In this function, if we find a valid neighbor, we immediately call the recursive function again for that neighbor before checking the other neighbors. This allow us to explore each path to its fullest before moving on to the next path.