Vultr DocsLatest Content

Pacific Atlantic Water Flow

Updated on 04 July, 2025
Pacific Atlantic Water Flow header image

Problem Statement

In the given problem, we have a unique geographical configuration: an m x n rectangular island bordered on two edges by the Pacific Ocean and on the opposite two by the Atlantic Ocean. The Pacific touches the left and top edges, whereas the Atlantic touches the right and bottom edges. The island itself is divided into square cells which form a matrix, with each cell's value representing its height above sea level.

Rainfall on the island can lead to water traveling from one cell to adjacent ones, particularly directed to either or both oceans. However, there is a rule for the flow: water can move to a neighboring cell if and only if the neighboring cell's elevation is equal to or less than that of the current cell.

The challenge is to compute all the matrix coordinates [r, c] from which water can simultaneously reach both the Pacific and Atlantic oceans. These results are to be returned as a 2D list.

Examples

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]]

Explanation:

The following cells can flow to the Pacific and Atlantic oceans, as shown below:
[0,4]: [0,4] -> Pacific Ocean
  [0,4] -> Atlantic Ocean
[1,3]: [1,3] -> [0,3] -> Pacific Ocean
  [1,3] -> [1,4] -> Atlantic Ocean
[1,4]: [1,4] -> [1,3] -> [0,3] -> Pacific Ocean
  [1,4] -> Atlantic Ocean
[2,2]: [2,2] -> [1,2] -> [0,2] -> Pacific Ocean
  [2,2] -> [2,3] -> [2,4] -> Atlantic Ocean
[3,0]: [3,0] -> Pacific Ocean
  [3,0] -> [4,0] -> Atlantic Ocean
[3,1]: [3,1] -> [3,0] -> Pacific Ocean
  [3,1] -> [4,1] -> Atlantic Ocean
[4,0]: [4,0] -> Pacific Ocean
[4,0] -> Atlantic Ocean
Note that there are other possible paths for these cells to flow to the Pacific and Atlantic oceans.

Example 2

Input:

heights = [[1]]

Output:

[[0,0]]

Explanation:

The water can flow from the only cell to the Pacific and Atlantic oceans.

Constraints

  • m == heights.length
  • n == heights[r].length
  • 1 <= m, n <= 200
  • 0 <= heights[r][c] <= 105

Approach and Intuition

  1. Initial Understanding:

    • The corners of the matrix have direct access to both oceans. For example, the top-right corner [0, n-1] can drain directly to both the Pacific (from the top edge) and Atlantic (from the right edge).
    • A cell will have access to both oceans if there are viable paths leading to both oceans from that cell. This makes it necessary to explore from each ocean inward to the cells that can feed into it.

  2. Travel Strategy:

    • Two separate lists track cells accessible from each ocean. Let's call them pacificReachable and atlanticReachable.
    • Perform a search from all cells adjacent to the Pacific, marking reachable cells. Repeat this process for the Atlantic.
    • The traversal can be efficiently done using Depth-First Search (DFS) or Breadth-First Search (BFS) from all border cells adjacent to each ocean. During this traversal, only move to cells that have an elevation greater than or equal to the current cell (emulating the water flow condition).

  3. Common Cells Calculation:

    • The cells that appear in both pacificReachable and atlanticReachable are the answer, as they can drain into both oceans.
    • A final compilation of these common cells, possibly by intersecting the sets or through a matrix of boolean flags, will yield the desired coordinates.

By following the above methodologies, the problem can be approached logically, maintaining efficiency even as the matrix size scales to its upper limits as governed by the given constraints. The essence of the solution lies in effectively mapping water flow paths from the edges inwards, ensuring every possible path is accounted for by adapting typical graph traversal strategies.

Solutions

  • Java
java 
class WaterFlow {
    private static final int[][] MOVEMENTS = new int[][]{{0, 1}, {1, 0}, {-1, 0}, {0, -1}};
    private int totalRows;
    private int totalCols;
    private int[][] heights;
    
    public List<List<Integer>> findCommonFlowPoints(int[][] grid) {
        // Verify if the grid is empty
        if (grid.length == 0 || grid[0].length == 0) {
            return new ArrayList<>();
        }
    
        // Initialize class variables
        totalRows = grid.length;
        totalCols = grid[0].length;
        heights = grid;
        boolean[][] canReachPacific = new boolean[totalRows][totalCols];
        boolean[][] canReachAtlantic = new boolean[totalRows][totalCols];
    
        // Start Depth First Search from the cells adjacent to both oceans
        for (int row = 0; row < totalRows; row++) {
            depthFirstSearch(row, 0, canReachPacific);
            depthFirstSearch(row, totalCols - 1, canReachAtlantic);
        }
        for (int col = 0; col < totalCols; col++) {
            depthFirstSearch(0, col, canReachPacific);
            depthFirstSearch(totalRows - 1, col, canReachAtlantic);
        }
    
        // Collect cells where water can flow to both oceans
        List<List<Integer>> result = new ArrayList<>();
        for (int row = 0; row < totalRows; row++) {
            for (int col = 0; col < totalCols; col++) {
                if (canReachPacific[row][col] && canReachAtlantic[row][col]) {
                    result.add(Arrays.asList(row, col));
                }
            }
        }
        return result;
    }
    
    private void depthFirstSearch(int row, int col, boolean[][] oceanReachable) {
        // Mark the cell as reachable
        oceanReachable[row][col] = true;
        for (int[] move : MOVEMENTS) {
            int newRow = row + move[0];
            int newCol = col + move[1];
            // Ensure the new position is within grid bounds
            if (newRow < 0 || newRow >= totalRows || newCol < 0 || newCol >= totalCols) {
                continue;
            }
            // Prevent revisiting and ensure flow is possible
            if (oceanReachable[newRow][newCol] || heights[newRow][newCol] < heights[row][col]) {
                continue;
            }
            depthFirstSearch(newRow, newCol, oceanReachable);
        }
    }
}

The provided Java solution tackles the problem of identifying points in a grid where water can flow both to the Pacific and Atlantic oceans. Here's the breakdown of how this solution works:

  • First, initializes necessary variables including a totalRows and totalCols based on input grid dimensions, and a heights array to store the grid values.
  • Two boolean matrices—canReachPacific and canReachAtlantic—track whether each cell is reachable from the respective ocean.
  • It uses a Depth First Search (DFS) method starting from the edges of the grid which are adjacent to the oceans:
    • For the Pacific, the DFS starts from the first row and first column of each row.
    • For the Atlantic, the DFS initiates from the last row and the last column of each row.
  • The depthFirstSearch function recursively explores neighboring cells. It marks a cell as true in the relevant ocean matrix if the cell hasn't been visited and its height is higher or equal to the current cell—ensuring water can only flow from high to equal or lower height.
  • Post DFS completion, the function iterates through the grid and collects coordinates of cells where both ocean matrices are marked true, indicating water can reach both oceans.

Results are aggregated and returned as a list of lists, where each inner list contains the row and column indices of a valid cell. This method effectively and efficiently finds all required points in the grid with the potential of water flow to both oceans employing the DFS logical framework.

  • Python
python 
class Solution:
    def waterFlow(self, heights: List[List[int]]) -> List[List[int]]:
        if not heights or not heights[0]:
            return []
            
        rows, cols = len(heights), len(heights[0])
        pacific = set()
        atlantic = set()
            
        def traverse(x, y, visited):
            visited.add((x, y))
            for dx, dy in [(1, 0), (0, 1), (-1, 0), (0, -1)]:
                nx, ny = x + dx, y + dy
                if nx < 0 or nx >= rows or ny < 0 or ny >= cols or (nx, ny) in visited:
                    continue
                if heights[nx][ny] < heights[x][y]:
                    continue
                traverse(nx, ny, visited)
            
        for i in range(rows):
            traverse(i, 0, pacific)
            traverse(i, cols - 1, atlantic)
        for j in range(cols):
            traverse(0, j, pacific)
            traverse(rows - 1, j, atlantic)
            
        return list(pacific & atlantic)

Solution Summary:

The provided Python3 code defines a solution to determine the cells in a matrix that can flow water to both the Pacific and Atlantic oceans. The matrix represents elevations, and water can only flow to lower or equal height neighbors.

  • Initialize pacific and atlantic sets to track cells that can reach respective oceans.
  • Define a helper function traverse to perform a depth-first search (DFS) starting from given coordinates. This function adds the current cell to the visited set and then iterates over the four possible directions (right, down, left, up). It checks:
    • If the new position is out of matrix bounds or already visited, skip to the next direction.
    • If the neighboring elevation is less than the current one, skip it since water cannot flow uphill.
    • If valid, recursively call traverse for the new position.
  • Loop over all cells on the edges which directly touch the oceans. For Pacific, traverse from the leftmost and top cells. For Atlantic, traverse from the rightmost and bottom cells.
  • Compute the intersection of sets (cells that connect to both oceans) and return it.

The solution efficiently explores all possible paths from the ocean-bound cells inward, marking those that can send water back to the ocean. By using sets for both oceans, it ensures that the results are unique and calculates the common cells using set intersection, reducing computational complexity.

Comments

No comments yet.