Pacific Atlantic Water Flow

Solutions

Depth-First Search

Time: O(m*n)Space: O(m*n)

The solution uses depth-first search to find all cells that can flow to both oceans. It starts by initializing two 2D arrays, pacific and atlantic, to keep track of the cells that can flow to the Pacific Ocean and the Atlantic Ocean, respectively. Then, it performs DFS from the cells on the borders of the matrix to mark the cells that can flow to the corresponding ocean. Finally, it iterates through the matrix to find the cells that can flow to both oceans and adds them to the result list.

function pacificAtlantic(heights) {
  let m = heights.length,
    n = heights[0].length,
    pacific = Array(m)
      .fill()
      .map(() => Array(n).fill(false)),
    atlantic = Array(m)
      .fill()
      .map(() => Array(n).fill(false));

  function dfs(i, j, visited, prevHeight) {
    if (
      i < 0 ||
      i >= m ||
      j < 0 ||
      j >= n ||
      visited[i][j] ||
      heights[i][j] < prevHeight
    )
      return;
    visited[i][j] = true;
    dfs(i - 1, j, visited, heights[i][j]);
    dfs(i + 1, j, visited, heights[i][j]);
    dfs(i, j - 1, visited, heights[i][j]);
    dfs(i, j + 1, visited, heights[i][j]);
  }
  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]);
  }
  let result = [];
  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;
}

Constraints:

Examples:

Solutions

Depth-First Search

Follow-up: