Pacific Atlantic Water Flow medium

Problem Statement

You are given an m x n integer matrix heights representing the height of each unit cell in a continent. The Pacific ocean touches the left and top edges of the continent, and the Atlantic ocean touches the right and bottom edges.

Water can only flow in four directions: up, down, left, and right. Water flows from a cell to an adjacent cell only if the height of the adjacent cell is not higher than the height of the current cell.

Find the cells from which water can flow to both the Pacific and Atlantic oceans. Return a list of coordinates, where the coordinates of a cell are represented as an array [row, col]. You may return the answer in any order.

Example 1

Input: heights = [[1,2,2,3,5],[3,2,3,4,4],[2,4,5,3,1],[6,7,1,4,5],[5,1,1,2,4]] Output: [[0,4],[1,3],[1,4],[2,2],[3,0],[3,1],[4,0]]

Example 2

Input: heights = [[1,1,1,1,1],[1,1,1,1,1],[1,1,1,1,1],[1,1,1,1,1]] Output: [[0,4],[1,4],[2,4],[3,4],[4,4],[4,3],[4,2],[4,1],[4,0],[3,0],[2,0],[1,0],[0,0]]

Steps

1. Initialization: Create two boolean matrices, pacific and atlantic, of the same size as heights. Initialize pacific to true for cells touching the Pacific (first row and first column), and atlantic to true for cells touching the Atlantic (last row and last column).

2. Depth-First Search (DFS): Perform DFS starting from cells touching the oceans. During the DFS, mark cells reachable from the ocean as true in the corresponding boolean matrix. The DFS function checks if a cell is within bounds, if its height is not greater than the current cell's height, and if it hasn't been visited yet.

3. Result: Iterate through the heights matrix. If a cell is marked as reachable from both the Pacific and Atlantic in both pacific and atlantic matrices, add its coordinates to the result list.

Explanation

The DFS function recursively explores the continent. It starts from the ocean-touching cells and explores adjacent cells with equal or lower heights. This process simulates the flow of water. By marking cells reachable from each ocean, we identify cells that can reach both.

Code

function pacificAtlantic(heights: number[][]): number[][] {
    const m = heights.length;
    const n = heights[0].length;
    const pacific = Array.from(Array(m), () => new Array(n).fill(false));
    const atlantic = Array.from(Array(m), () => new Array(n).fill(false));
    const result: number[][] = [];

    const dfs = (row: number, col: number, ocean: boolean[][], prevHeight: number) => {
        if (row < 0 || row >= m || col < 0 || col >= n || ocean[row][col] || heights[row][col] < prevHeight) return;
        ocean[row][col] = true;
        dfs(row + 1, col, ocean, heights[row][col]);
        dfs(row - 1, col, ocean, heights[row][col]);
        dfs(row, col + 1, ocean, heights[row][col]);
        dfs(row, col - 1, ocean, heights[row][col]);
    };

    // Initialize Pacific and Atlantic reachable cells
    for (let i = 0; i < m; i++) {
        dfs(i, 0, pacific, heights[i][0]);
        dfs(i, n - 1, atlantic, heights[i][n - 1]);
    }
    for (let j = 0; j < n; j++) {
        dfs(0, j, pacific, heights[0][j]);
        dfs(m - 1, j, atlantic, heights[m - 1][j]);
    }

    // Find cells reachable from both oceans
    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            if (pacific[i][j] && atlantic[i][j]) {
                result.push([i, j]);
            }
        }
    }

    return result;
}

Complexity

• Time Complexity: O(m * n), where 'm' and 'n' are the dimensions of the matrix. This is because we visit each cell at most once during the DFS.
• Space Complexity: O(m * n) to store the pacific and atlantic matrices, and potentially O(m * n) for the recursion stack in the worst-case scenario (though it's often less in practice). The result list also takes O(m*n) in the worst case.