Pacific Atlantic Water Flow

Med

#0404Time: O((m*n)^2). For each of the `m*n` cells, we perform a DFS. In the worst-case scenario, the DFS might have to visit all `m*n` cells. This leads to a quadratic time complexity.Space: O(m*n). For each of the `m*n` starting cells, a new `visited` matrix of size `m*n` is created. The recursion stack for the DFS can also go up to `m*n` deep in the worst case.3 companies

Algorithms

Depth-First Search Breadth-First Search

Data structures

Array Matrix

Companies

Nutanix ServiceNow Coupang

Prompt

There is an m x n rectangular island that borders both the Pacific Ocean and Atlantic Ocean. The Pacific Ocean touches the island's left and top edges, and the Atlantic Ocean touches the island's right and bottom edges.

The island is partitioned into a grid of square cells. You are given an m x n integer matrix heights where heights[r][c] represents the height above sea level of the cell at coordinate (r, c).

The island receives a lot of rain, and the rain water can flow to neighboring cells directly north, south, east, and west if the neighboring cell's height is less than or equal to the current cell's height. Water can flow from any cell adjacent to an ocean into the ocean.

Return a 2D list of grid coordinates result where result[i] = [r_i, c_i] denotes that rain water can flow from cell (r_i, c_i) to both the Pacific and Atlantic oceans.

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] <= 10⁵

Approaches

2 approaches with complexity analysis and trade-offs.

This approach directly simulates the water flow for each individual cell on the island. We iterate through every cell (r, c) and, for each one, perform a search, such as Depth-First Search (DFS), to determine if water from this specific cell can find a path to both the Pacific and Atlantic oceans.

Algorithm

Initialize an empty list result.
Iterate through each cell (r, c) in the m x n grid.
For each cell, perform a Depth-First Search (DFS) to check if it can reach both oceans.
The DFS needs to keep track of visited cells for the current starting cell to avoid infinite loops.
The DFS also needs to track if a Pacific border (row 0 or col 0) and an Atlantic border (row m-1 or col n-1) have been reached.
The DFS can only move from a cell (r1, c1) to a neighbor (r2, c2) if heights[r2][c2] <= heights[r1][c1].
If the DFS from (r, c) confirms reachability to both oceans, add [r, c] to the result list.
Return result after checking all cells.

Walkthrough

The algorithm iterates through every single cell of the heights matrix. For each cell, it initiates a new traversal (like DFS or BFS) to explore all possible paths water could take flowing downwards. A visited array is used for each traversal to prevent getting stuck in cycles. During a traversal starting from (r, c), we keep track of whether we have reached a Pacific-bordering cell (top or left edge) and an Atlantic-bordering cell (bottom or right edge). If paths to both oceans are found, the starting cell (r, c) is added to the result list, and we move on to test the next cell in the grid.

1class Solution {2    int m, n;3    int[][] heights;4    int[] dr = {-1, 1, 0, 0};5    int[] dc = {0, 0, -1, 1};6 7    public List<List<Integer>> pacificAtlantic(int[][] heights) {8        this.heights = heights;9        this.m = heights.length;10        if (m == 0) return new ArrayList<>();11        this.n = heights[0].length;12        if (n == 0) return new ArrayList<>();13        14        List<List<Integer>> result = new ArrayList<>();15        for (int i = 0; i < m; i++) {16            for (int j = 0; j < n; j++) {17                // For each cell, run a DFS to check reachability to both oceans18                boolean[] reaches = new boolean[2]; // reaches[0] for Pacific, reaches[1] for Atlantic19                dfs(i, j, new boolean[m][n], reaches);20                if (reaches[0] && reaches[1]) {21                    result.add(Arrays.asList(i, j));22                }23            }24        }25        return result;26    }27 28    private void dfs(int r, int c, boolean[][] visited, boolean[] reaches) {29        if (visited[r][c]) {30            return;31        }32        visited[r][c] = true;33 34        if (r == 0 || c == 0) {35            reaches[0] = true;36        }37        if (r == m - 1 || c == n - 1) {38            reaches[1] = true;39        }40 41        // Explore neighbors42        for (int i = 0; i < 4; i++) {43            int nr = r + dr[i];44            int nc = c + dc[i];45            46            if (nr >= 0 && nr < m && nc >= 0 && nc < n &&47                !visited[nr][nc] && heights[nr][nc] <= heights[r][c]) {48                dfs(nr, nc, visited, reaches);49            }50        }51    }52}

Complexity

Time

O((m*n)^2). For each of the `m*n` cells, we perform a DFS. In the worst-case scenario, the DFS might have to visit all `m*n` cells. This leads to a quadratic time complexity.

Space

O(m*n). For each of the `m*n` starting cells, a new `visited` matrix of size `m*n` is created. The recursion stack for the DFS can also go up to `m*n` deep in the worst case.

Trade-offs

Pros

Conceptually straightforward as it directly models the question's premise.

Cons

Extremely inefficient due to massive amounts of redundant computation. The same paths are explored repeatedly for different starting cells.
Will likely result in a 'Time Limit Exceeded' (TLE) error for larger grid sizes.

A much more efficient approach is to reverse the problem. Instead of checking where water can flow to from each cell, we find which cells can be reached by water flowing from the oceans. We can think of this as water flowing 'uphill' from the ocean shores. The cells that can be reached by both oceans are our answer.

Algorithm

Initialize two boolean m x n matrices, pacificReachable and atlanticReachable, to false.
Create a helper DFS function dfs(r, c, visited, prevHeight) that explores cells reachable by 'uphill' flow.
Pacific Search: Start a DFS from every cell on the Pacific border (top and left edges). Mark all reachable cells in pacificReachable as true. The DFS can only move from cell A to cell B if height(B) >= height(A).
Atlantic Search: Similarly, start a DFS from every cell on the Atlantic border (bottom and right edges). Mark all reachable cells in atlanticReachable as true.
Find Intersection: Iterate through the entire grid. If a cell (r, c) is true in both pacificReachable and atlanticReachable, add it to the final result list.
Return the result list.

Walkthrough

This method avoids redundant calculations by starting the search from the oceans and flowing inwards. We perform two separate multi-source traversals (using DFS or BFS).

Pacific Flow: We identify all cells that can flow to the Pacific. We do this by starting a search from all cells on the Pacific border (row 0 and column 0) and finding all cells that can reach them. The condition for traversal is reversed: we can move from cell A to an adjacent cell B if height(B) >= height(A). We use a pacificReachable boolean matrix to mark all such cells.
Atlantic Flow: We do the same for the Atlantic Ocean. We start a search from all cells on the Atlantic border (last row and last column) and mark all reachable cells in an atlanticReachable matrix.
Result: The final answer is the set of cells that are marked as reachable in both matrices. We can find this by iterating through the grid and collecting coordinates (r, c) where pacificReachable[r][c] and atlanticReachable[r][c] are both true.

1class Solution {2    public List<List<Integer>> pacificAtlantic(int[][] heights) {3        List<List<Integer>> result = new ArrayList<>();4        if (heights == null || heights.length == 0 || heights[0].length == 0) {5            return result;6        }7 8        int m = heights.length;9        int n = heights[0].length;10 11        boolean[][] pacificReachable = new boolean[m][n];12        boolean[][] atlanticReachable = new boolean[m][n];13 14        // Start DFS from all Pacific border cells15        for (int i = 0; i < m; i++) {16            dfs(i, 0, pacificReachable, Integer.MIN_VALUE, heights);17        }18        for (int j = 1; j < n; j++) {19            dfs(0, j, pacificReachable, Integer.MIN_VALUE, heights);20        }21 22        // Start DFS from all Atlantic border cells23        for (int i = 0; i < m; i++) {24            dfs(i, n - 1, atlanticReachable, Integer.MIN_VALUE, heights);25        }26        for (int j = 0; j < n - 1; j++) {27            dfs(m - 1, j, atlanticReachable, Integer.MIN_VALUE, heights);28        }29 30        // Find the intersection of the two sets of reachable cells31        for (int i = 0; i < m; i++) {32            for (int j = 0; j < n; j++) {33                if (pacificReachable[i][j] && atlanticReachable[i][j]) {34                    result.add(Arrays.asList(i, j));35                }36            }37        }38        return result;39    }40 41    private void dfs(int r, int c, boolean[][] visited, int prevHeight, int[][] heights) {42        int m = heights.length;43        int n = heights[0].length;44 45        if (r < 0 || r >= m || c < 0 || c >= n || visited[r][c] || heights[r][c] < prevHeight) {46            return;47        }48 49        visited[r][c] = true;50        int currentHeight = heights[r][c];51 52        dfs(r + 1, c, visited, currentHeight, heights);53        dfs(r - 1, c, visited, currentHeight, heights);54        dfs(r, c + 1, visited, currentHeight, heights);55        dfs(r, c - 1, visited, currentHeight, heights);56    }57}

Complexity

Time

O(m*n). We run two separate multi-source DFS traversals. Each traversal visits each cell at most once. The first traversal for the Pacific costs O(m*n), and the second for the Atlantic costs O(m*n). The final iteration to find the intersection also costs O(m*n). The total time is linear with respect to the number of cells.

Space

O(m*n). We use two boolean matrices of size `m*n` to store reachability. The recursion stack for DFS can also reach a depth of O(m*n) in the worst case.

Trade-offs

Pros

Highly efficient with linear time complexity.
Avoids all redundant computations by solving for all cells in just two main traversals.

Cons

Requires extra space for two m x n boolean matrices.
The logic is less direct and requires thinking about the problem in reverse, which can be less intuitive.

Solutions

Solution

1class Solution { private int [][] heights ; private int m ; private int n ; public List < List < Integer >> pacificAtlantic ( int [][] heights ) { m = heights . length ; n = heights [ 0 ]. length ; this . heights = heights ; Deque < int []> q1 = new LinkedList <>(); Deque < int []> q2 = new LinkedList <>(); Set < Integer > vis1 = new HashSet <>(); Set < Integer > vis2 = new HashSet <>(); for ( int i = 0 ; i < m ; ++ i ) { for ( int j = 0 ; j < n ; ++ j ) { if ( i == 0 || j == 0 ) { vis1 . add ( i * n + j ); q1 . offer ( new int [] { i , j }); } if ( i == m - 1 || j == n - 1 ) { vis2 . add ( i * n + j ); q2 . offer ( new int [] { i , j }); } } } bfs ( q1 , vis1 ); bfs ( q2 , vis2 ); List < List < Integer >> ans = new ArrayList <>(); for ( int i = 0 ; i < m ; ++ i ) { for ( int j = 0 ; j < n ; ++ j ) { int x = i * n + j ; if ( vis1 . contains ( x ) && vis2 . contains ( x )) { ans . add ( Arrays . asList ( i , j )); } } } return ans ; } private void bfs ( Deque < int []> q , Set < Integer > vis ) { int [] dirs = {- 1 , 0 , 1 , 0 , - 1 }; while (! q . isEmpty ()) { for ( int k = q . size (); k > 0 ; -- k ) { int [] p = q . poll (); for ( int i = 0 ; i < 4 ; ++ i ) { int x = p [ 0 ] + dirs [ i ]; int y = p [ 1 ] + dirs [ i + 1 ]; if ( x >= 0 && x < m && y >= 0 && y < n && ! vis . contains ( x * n + y ) && heights [ x ][ y ] >= heights [ p [ 0 ]][ p [ 1 ]]) { vis . add ( x * n + y ); q . offer ( new int [] { x , y }); } } } } } }

1typedef pair < int , int > pii ; class Solution { public: vector < vector < int >> heights ; int m ; int n ; vector < vector < int >> pacificAtlantic ( vector < vector < int >>& heights ) { m = heights . size (); n = heights [ 0 ]. size (); this -> heights = heights ; queue < pii > q1 ; queue < pii > q2 ; unordered_set < int > vis1 ; unordered_set < int > vis2 ; for ( int i = 0 ; i < m ; ++ i ) { for ( int j = 0 ; j < n ; ++ j ) { if ( i == 0 || j == 0 ) { vis1 . insert ( i * n + j ); q1 . emplace ( i , j ); } if ( i == m - 1 || j == n - 1 ) { vis2 . insert ( i * n + j ); q2 . emplace ( i , j ); } } } bfs ( q1 , vis1 ); bfs ( q2 , vis2 ); vector < vector < int >> ans ; for ( int i = 0 ; i < m ; ++ i ) { for ( int j = 0 ; j < n ; ++ j ) { int x = i * n + j ; if ( vis1 . count ( x ) && vis2 . count ( x )) { ans . push_back ({ i , j }); } } } return ans ; } void bfs ( queue < pii >& q , unordered_set < int >& vis ) { vector < int > dirs = { - 1 , 0 , 1 , 0 , - 1 }; while ( ! q . empty ()) { for ( int k = q . size (); k > 0 ; -- k ) { auto p = q . front (); q . pop (); for ( int i = 0 ; i < 4 ; ++ i ) { int x = p . first + dirs [ i ]; int y = p . second + dirs [ i + 1 ]; if ( x >= 0 && x < m && y >= 0 && y < n && ! vis . count ( x * n + y ) && heights [ x ][ y ] >= heights [ p . first ][ p . second ]) { vis . insert ( x * n + y ); q . emplace ( x , y ); } } } } } };

1class Solution:2    def pacificAtlantic(self, heights: List[List[int]]) -> List[List[int]]: def bfs(q, vis): while q: for _ in range(len(q)): i, j = q . popleft() for a, b in [[0, - 1], [0, 1], [1, 0], [- 1, 0]]: x, y = i + a, j + b if (0 <= x < m and 0 <= y < n and (x, y) not in vis and heights[x][y] >= heights[i][j]): vis . add((x, y)) q . append((x, y)) m, n = len(heights), len(heights[0]) vis1, vis2 = set(), set() q1 = deque() q2 = deque() for i in range(m): for j in range(n): if i == 0 or j == 0: vis1 . add((i, j)) q1 . append((i, j)) if i == m - 1 or j == n - 1: vis2 . add((i, j)) q2 . append((i, j)) bfs(q1, vis1) bfs(q2, vis2) return [(i, j) for i in range(m) for j in range(n) if (i, j) in vis1 and (i, j) in vis2]

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem