Pacific Atlantic Water Flow

Asked byGoogleUberAmazonSalesforce

Problem

Given an m x n grid of heights representing a continent bordered by the Pacific Ocean on the top and left edges and the Atlantic Ocean on the bottom and right edges, water can flow from a cell to a neighboring cell only if the neighbor's height is less than or equal to the current cell. Return the list of cells from which water can reach both oceans.

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

Constraints

1 <= m, n <= 200

Solve it in the editor. Sign in free to run your Python or JavaScript against test cases, get a verdict, and track your attempts.

Solve on FeatCode →

How to approach it: the Graphs pattern

A graph models relationships as nodes and edges, which can be directed or undirected, weighted or not. Most graph problems come down to choosing the right traversal — DFS, BFS, or union-find — for what you're trying to find.

Look for this pattern when

The problem involves connections between items (islands, courses with prerequisites, friend networks, grids).
You need the shortest path in an unweighted graph (BFS) or need to explore every reachable node (DFS).
You're asking "are these two things connected?" repeatedly (union-find).

Read the full Graphs guide →

Video walkthroughs

Original problem on LeetCode ↗