What is the brute force approach and complexity for Pacific Atlantic Water Flow?

For each cell, run a fresh downhill search; keep the cell if the search reaches both oceans with time complexity O((m · n)²) and space complexity O(m · n).

What is the optimal approach and complexity for Pacific Atlantic Water Flow?

Walk uphill from the Pacific edge and from the Atlantic edge; the answer is the cells both reach with optimal time complexity O(m · n) and space complexity O(m · n).

How do you identify the pattern for Pacific Atlantic Water Flow?

Look for key signals in the prompt: "flow to the Pacific and to the Atlantic" indicates Two oceans means two separate searches, one for each ocean.; "the same height or lower" indicates Water runs downhill. Reversed, the search climbs, so the neighbour must be at least as high.; "reach both oceans" indicates The answer is the overlap of two reached sets..

Pacific Atlantic Water Flow

Medium·LeetCode #417 Pro OnlyInterview-Level

LeetCode

Problem Statement

You are given a grid of heights for an island. The Pacific Ocean touches the top and left edges, and the Atlantic Ocean touches the bottom and right edges. Water flows from a cell to a neighbour (up, down, left or right) when that neighbour is the same height or lower. Water can also flow from any edge cell into the ocean that touches it. Return every cell from which water can reach both oceans.

Input

heights, an m × n grid of integers. heights[r][c] is the height of the cell at row r, column c.

Output

A list of [row, col] pairs, one for each cell that can reach both oceans. The pairs may come in any order.

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

Each listed cell reaches both oceans. For example, (1,3) flows up to (0,3), which touches the Pacific, and right to (1,4), which touches the Atlantic.

Example 2

Input: heights = [[1]]

Output: [[0,0]]

The single cell touches both oceans.

Constraints

• 1 ≤ m, n ≤ 200, where m is the number of rows and n is the number of columns
• 0 ≤ heights[r][c] ≤ 10^5

Pattern Recognition Clues

Recognising these key signals in the problem description immediately identifies the pattern:

“flow to the Pacific and to the Atlantic”

→ Two oceans means two separate searches, one for each ocean.

“the same height or lower”

→ Water runs downhill. Reversed, the search climbs, so the neighbour must be at least as high.

“reach both oceans”

→ The answer is the overlap of two reached sets.

Approach Complexity Ladder

Brute Force — from every cell, flow downhill and check both oceansO((m · n)²)O(m · n)

For each cell, run a fresh downhill search; keep the cell if the search reaches both oceans

Optimal — climb from each ocean's edge, keep the cells both climbs reachO(m · n)O(m · n)

Walk uphill from the Pacific edge and from the Atlantic edge; the answer is the cells both reach

Brute Force Intuition

For each cell, run a search that moves to neighbours that are the same height or lower. If the search reaches a top or left edge cell and a bottom or right edge cell, the start reaches both oceans. Every cell runs its own search, so the same downhill paths are walked again and again.

Recognition rule for this sub-pattern:

Start a DFS/BFS from each unvisited cell; everything it reaches is one component.

Remember this · Graph BFS / DFS

Trigger

Grid of cells, islands, regions, "minimum steps", transformations between states, connected components.

Think

What is a node, what is an edge, and do I need the shortest path or just reachability?

Key question

How do I mark visited so I never process a node twice?

Brute2Best Pro Content

Unlock Complete Visual Walkthrough & Optimal C++

The interactive animated dry-run player, optimized C++ implementation, state invariant derivations, and edge-case breakdown for this question are part of Brute2Best Pro. The anchor question of every sub-pattern is completely free.

All 440 visual dry runs & algorithms

Interactive step-by-step playback with pointer & array state transitions

52 comprehensive LLD chapters

Interactive UML diagrams, real-world stories (Food Delivery, Trading, RPG), and practice solutions

40 C++ basics labs & hardware memory models

Vtables, byte layouts, assembly insights, and multi-threading race conditions

Production-ready C++23 source code

Modern idioms, clean contracts, time/space complexity derivations, and interview takeaways

Create Free Account Log in

First anchor question per pattern, Part 1 LLD & Module 1 C++ basics are 100% Free forever.

Beyond The LeetCode Problem

How this concept connects to System Design & C++ Systems

Bridge DSA with production engineering

Top engineering interviews test whether you understand how algorithms like Graph BFS / DFS translate into production architectures and low-level memory mechanics.

LLD Real-World Story

Food Delivery System (Zomato / DoorDash)

Geospatial indexing and shortest dispatch routing for delivery partners.

Explore Track

C++ Internals

Virtual Method Table (vtable) & Dynamic Dispatch

Polymorphic graph nodes and state machine execution overhead.

Explore Track

Surrounded Regions