Pacific Atlantic Water Flow: Exploring Water Movement in a Matrix

The "Pacific Atlantic Water Flow" problem is a unique challenge that combines elements of graph theory and depth-first search (DFS) in a matrix setting.

Problem Statement

Given an m x n matrix of non-negative integers representing the height of each unit cell in a continent, determine the list of grid coordinates where water can flow to both the Pacific and Atlantic oceans. Water can only flow in four directions (up, down, left, or right) from a cell to another one with height equal or lower.

Example

Consider a matrix: Pacific ~ ~ ~ ~ ~ ~ 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 *

• • • • Atlantic

The cells marked with * are the ones where water can flow to both oceans.

Depth-First Search Solution

function pacificAtlantic(heights) {
  if (!heights || !heights.length) return [];

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

  function dfs(row, col, ocean) {
    if (ocean[row][col]) return;
    ocean[row][col] = true;

    [
      [-1, 0],
      [1, 0],
      [0, -1],
      [0, 1],
    ].forEach(([dr, dc]) => {
      const newRow = row + dr,
        newCol = col + dc;
      if (
        newRow >= 0 &&
        newRow < m &&
        newCol >= 0 &&
        newCol < n &&
        heights[newRow][newCol] >= heights[row][col]
      ) {
        dfs(newRow, newCol, ocean);
      }
    });
  }

  for (let i = 0; i < m; i++) {
    dfs(i, 0, pacific);
    dfs(i, n - 1, atlantic);
  }
  for (let i = 0; i < n; i++) {
    dfs(0, i, pacific);
    dfs(m - 1, i, atlantic);
  }

  const 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;
}

Breaking Down the Solution

• Initialize Oceans: Create two matrices, pacific and atlantic, to track the cells reachable from each ocean.
• Depth-First Search: Perform DFS from the edges of the matrix towards the interior. Mark cells reachable from each ocean in their respective matrices.
• Collect Results: Iterate over the entire matrix, and for each cell reachable from both oceans, add its coordinates to the result list.

Conclusion

The Pacific Atlantic Water Flow problem showcases the application of DFS in matrix traversal and is an excellent example of how to handle complex flow and reachability problems in a grid. It emphasizes depth-first search's versatility in exploring paths and conditions in a matrix.