Learning Journal

2/21/2024

Pacific Atlantic Water Flow - Breadth First Search

Tags: algorithms leetcode graph breadth_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 pacificQueue = new MyQueue(NUM_ROWS * NUM_COLS*2);
    const atlanticQueue = new MyQueue(NUM_ROWS * NUM_COLS*2);    

    for(let row = 0; row < NUM_ROWS; row++) {
        pacificQueue.enqueue([row, 0]);
        atlanticQueue.enqueue([row, NUM_COLS - 1])
    }

    for(let col = 0; col < NUM_COLS; col++) {
        pacificQueue.enqueue([0, col]);
        atlanticQueue.enqueue([NUM_ROWS - 1, col])
    }


    const reachablePacific:boolean[][] = scan(pacificQueue);


    const reachableAtlantic:boolean[][] = scan(atlanticQueue);
    

    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(queue: MyQueue):boolean[][] {
        const reachable:boolean[][] = Array(NUM_ROWS).fill(0).map(_ => Array(NUM_COLS).fill(false));

        while(!queue.isEmpty()) {
            const curCell = queue.dequeue();
            reachable[curCell[0]][curCell[1]] = true;


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

                if(nextRow >= 0 && nextRow < NUM_ROWS 
                    && nextCol >= 0 && nextCol < NUM_COLS
                    && !reachable[nextRow][nextCol] 
                    && heights[nextRow][nextCol] >= heights[curCell[0]][curCell[1]]){
                    queue.enqueue([nextRow, nextCol]);
                }
            }
            
        }



        return reachable;
    }
};


class MyQueue {
    private readonly arr:number[][];
    private start:number = 0;
    private end:number = 0;

    constructor(length:number) {
        this.arr = Array(length).fill(0).map(_ => [-1,-1]);
    }

    public isEmpty(): boolean {
        return this.arr[this.end][0] === -1 && this.start === this.end;
    }

    public isFull():boolean {
        return this.arr[this.end][0] !== -1;
    }


    public enqueue(cord:number[]):void {
        
        this.arr[this.end] = cord;
        this.end++;

        if(this.end === this.arr.length)
            this.end = 0;
        
    }

    public dequeue():number[] {

        const val = this.arr[this.start];
        this.arr[this.start] = [-1,-1];
        this.start++;

        if(this.start === this.arr.length){
            this.start = 0;
        }

        return val;
    }

}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 pacificQueue = new MyQueue(NUM_ROWS * NUM_COLS*2);
    const atlanticQueue = new MyQueue(NUM_ROWS * NUM_COLS*2);    

    for(let row = 0; row < NUM_ROWS; row++) {
        pacificQueue.enqueue([row, 0]);
        atlanticQueue.enqueue([row, NUM_COLS - 1])
    }

    for(let col = 0; col < NUM_COLS; col++) {
        pacificQueue.enqueue([0, col]);
        atlanticQueue.enqueue([NUM_ROWS - 1, col])
    }


    const reachablePacific:boolean[][] = scan(pacificQueue);


    const reachableAtlantic:boolean[][] = scan(atlanticQueue);
    

    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(queue: MyQueue):boolean[][] {
        const reachable:boolean[][] = Array(NUM_ROWS).fill(0).map(_ => Array(NUM_COLS).fill(false));

        while(!queue.isEmpty()) {
            const curCell = queue.dequeue();
            reachable[curCell[0]][curCell[1]] = true;


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

                if(nextRow >= 0 && nextRow < NUM_ROWS 
                    && nextCol >= 0 && nextCol < NUM_COLS
                    && !reachable[nextRow][nextCol] 
                    && heights[nextRow][nextCol] >= heights[curCell[0]][curCell[1]]){
                    queue.enqueue([nextRow, nextCol]);
                }
            }
            
        }



        return reachable;
    }
};


class MyQueue {
    private readonly arr:number[][];
    private start:number = 0;
    private end:number = 0;

    constructor(length:number) {
        this.arr = Array(length).fill(0).map(_ => [-1,-1]);
    }

    public isEmpty(): boolean {
        return this.arr[this.end][0] === -1 && this.start === this.end;
    }

    public isFull():boolean {
        return this.arr[this.end][0] !== -1;
    }


    public enqueue(cord:number[]):void {
        
        this.arr[this.end] = cord;
        this.end++;

        if(this.end === this.arr.length)
            this.end = 0;
        
    }

    public dequeue():number[] {

        const val = this.arr[this.start];
        this.arr[this.start] = [-1,-1];
        this.start++;

        if(this.start === this.arr.length){
            this.start = 0;
        }

        return val;
    }

}

PROBLEM

This is my breadth-first search approach for this problem.

At first, I thought the queue's length is atmost the number of cells, but it turned out not the case. The reason is that you can add one cell multiple time to the queue. The first time you add is because there is a path to the ocean that going through cell A. Then, you check cell B and it turns out that there is also a path going through that cell to the ocean. So, you might check one cell multiple times. To eliminate the redundancy, I guess, we can use a hash table to keep track of which cells that we already checked.

Another thing that I noticed when implementing the queue is that, it is not necessary empty when this.start === this.end because it can be full and the end pointer goes around then meets start again. That is why we need to check if both of them point to an empty slot.

Revised by ChatGPT

This is my breadth-first search approach for this problem.

Initially, I thought the queue's length would be atmost the number of cells. However, this is not the case because one cell can be added to the queue multiple times. For example, you might add a cell to the queue because there is a path to the ocean that goes through cell A. Later, you might find that there is also a path to the ocean that goes through cell B, which leads back to cell A. As a result, cell A could be checked multiple times. To eliminate this redundancy, we can use a hash table to keep track of which cells we have already checked.

Another thing I noticed when implementing the queue is that it is not necessarily empty when this.start === this.end. This is because the queue can be full, and the end pointer might loop around and meet the start pointer again. In this case, both pointers would point to a filled slot, not an empty one. To accurately determine if the queue is empty, we need to check if the slot pointed to by the end pointer is empty (this.arr[this.end][0] === 1) and if the start and end pointers are at the same position (this.start === this.end).