Search
⌘K
PricingBecome a Coach
Search
⌘K
Get Premium
Depth-First Search

Pacific Atlantic Water Flow

medium
DESCRIPTION (inspired by Leetcode.com)

You are given an m x n matrix of non-negative integers representing a grid of land, where rain falls on every cell. Each value in the grid represents the height of that piece of land.

The Pacific Ocean touches the left and top edges of the matrix, while the Atlantic Ocean touches the right and bottom edges. Water can only flow from a cell to its neighboring cells directly north, south, east, or west, but only if the height of the neighboring cell is equal to or lower than the current cell.

1223323432453245PacificAtlanticPacificAtlantic
Water can flow from grid[3][2] to the neighboring cells with a lower height.

Write a function to return a list of grid coordinates (i, j) where water can flow to both the Pacific and Atlantic Oceans. Water can flow from all cells directly adjacent to the ocean into that ocean.

Example 1:

Input:

grid = [
    [1, 2, 3],
    [4, 5, 6],
    [7, 8, 9]
]
123456789PacificPacificAtlanticAtlantic
Water can flow from the cells with circles above to both the Pacific and Atlantic Oceans

Output:

[
    [0, 2],
    [1, 2],
    [2, 0],
    [2, 1],
    [2, 2]
]

Explanation

To solve this question, we need to traverse the grid to find all cells where water can flow to both the Pacific and Atlantic Oceans, and then find the cells that are contained in both those sets.

Approach 1: Brute Force Approach

Let's focus on how to find all the cells that are reachable from an ocean. One straightforward approach is to iterate over each cell in the graph, and then check if there is a valid path from that cell to the ocean. If there is, we can add it to a set (depending on if it reaches the Pacific or Atlantic Ocean). After iterating over each cell, we can return the intersection of those two sets.
Solution
class Solution:
    def pacificAtlantic(self, matrix):
        if not matrix or not matrix[0]:
            return []
        rows, cols = len(matrix), len(matrix[0])
        pacific = set()
        atlantic = set()
        # Try to find a path from r, c to the Pacific or Atlantic ocean
        # via neighboring cells with lower heights
        def dfs(start_r, start_c, r, c, visited):
            if (r, c) in visited:
                return
            
            visited[(r, c)] = True
            if r == 0 or c == 0:
                pacific.add((start_r, start_c))
            if r == rows - 1 or c == cols - 1:
                atlantic.add((start_r, start_c))
            directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]
            for dr, dc in directions:
                nr, nc = r + dr, c + dc
                if 0 <= nr < rows and 0 <= nc < cols and matrix[nr][nc] <= matrix[r][c]:
                    dfs(start_r, start_c, nr, nc, visited)
                    visited[(nr, nc)] = False
        # Perform full DFS from each cell.
        for r in range(rows):
            for c in range(cols):
                visited = {}
                dfs(r, c, r, c, visited)
                
        return list(pacific & atlantic)
The problem with this approach is that it is very inefficient. For each cell, we have to perform a full DFS traversal of the entire grid in the worst case, resulting in a run-time of O((m x n)2).

Approach 2: Boundary DFS

The brute-force approach is inefficient because there is a lot of repeat work being done. For example, we have to calculate parts of the same path multiple times as we check if there is a valid path from a cell to the ocean.
123456789PacificPacificAtlantic 123456789PacificAtlantic 123456789PacificAtlanticAtlantic
The three seperate calls to dfs in the brute-force solution above would calculate parts of the same path multiple times.
A more efficient approach is to use "boundary DFS". With this approach, we "invert" the problem by starting from all cells adjacent to each ocean, and then use DFS to find cells that can flow into that cell. All the cells that we visit during each of these traversals are the set of cells that can flow into the ocean that the DFS originated from.
This is more efficient because it reduces redundant work - once we visit a cell using this traversal, we can mark it as visited so it is not visited by future traversals.
At the end, we can return the intersection of both sets to get the final answer.

Solution

Solution
class Solution:
    def pacific_atlantic_flow(self, grid): 
        if not grid or not grid[0]:
            return []
        rows, cols = len(grid), len(grid[0])
        # Step 1: Initialize empty sets
        pacific_reachable = set()
        atlantic_reachable = set()
        def dfs(r, c, reachable):
            reachable.add((r, c))
            for dr, dc in [(1,0), (-1,0), (0,1), (0,-1)]:
                nr, nc = r + dr, c + dc
                if 0 <= nr < rows and 0 <= nc < cols:
                    if (nr, nc) not in reachable and grid[nr][nc] >= grid[r][c]:
                        dfs(nr, nc, reachable)
        # initializes DFS from all cells in the Atlantic and Pacific Oceans
        # Note how we share a single visited set
        # across DFS calls that originate from the same ocean
        for r in range(rows):
            dfs(r, 0, pacific_reachable)
            dfs(r, cols - 1, atlantic_reachable)
        for c in range(cols):
            dfs(0, c, pacific_reachable)
            dfs(rows - 1, c, atlantic_reachable)
        # return the intersection of both sets.
        return list(pacific_reachable & atlantic_reachable)
Test Your Knowledge

Login to take the complexity quiz and track your progress

Complexity Analysis

Time Complexity: O(m * n) where m is the number of rows and n is the number of columns. We visit each cell once across all DFS calls that originate from a particular ocean. In the worst case, this means we visit each cell twice.

Space Complexity: O(m * n) where m is the number of rows and n is the number of columns. This is for the two visited sets that we have to maintain for the DFS traversals.

Mark as read

Next: Breadth-First Search Introduction

Your account is free and you can post anonymously if you choose.

Unlock Premium Coding Content

Interactive algorithm visualizations
Guided Practice
Recent interview questions
Learn More
Reading Progress

On This Page

Explanation

Approach 1: Brute Force Approach

Approach 2: Boundary DFS

Solution

Questions
Meta SWE Interview QuestionsAmazon SWE Interview QuestionsGoogle SWE Interview QuestionsOpenAI SWE Interview QuestionsEngineering Manager (EM) Interview Questions
Learn
Learn System DesignLearn DSALearn BehavioralLearn ML System DesignLearn Low Level DesignGuided Practice
Links
FAQPricingGift Mock InterviewsGift PremiumBecome a CoachOur CoachesHello Interview Premium
Legal
Terms and ConditionsPrivacy Policy
Contact
About UsProduct Support

7511 Greenwood Ave North Unit #4238 Seattle WA 98103

© 2026 Optick Labs Inc. All rights reserved.