DSA sheet · Graphs · Grid traversal · start from the border (reverse flow)

Pacific Atlantic Water Flow

Rain falls on an island of heights; water runs downhill to two oceans. Which cells can send water to both oceans? Trying every cell one by one is slow. The teacher's key move is the same one we used in Surrounded Regions: start from the border (the ocean side) and walk inwards, but with the flow rule reversed, so water "climbs" from the sea. One climb from the Pacific border fills a Pacific grid, one climb from the Atlantic border fills an Atlantic grid, and the answer is every cell marked in both. She calls this question very important for interviews.

Every part below follows the same order:
① the question in simple words → ② what the constraints tell us → ③ intuition → ④ building the logic from examples → ⑤ approach steps → ⑥ code → ⑦ code line by line → ⑧ dry run → ⑨ complexity & remember

• Part 0 · Graph and grid basics this page needs
• Part A · Brute force: follow the water from every cell
• Part B · Reverse DFS from both borders (the teacher's code)
• Part C · The same thing with BFS
• Part D · Revision page

Part 0 · Graph and grid basics this page needs

Nodes, edges, directed, undirected, weighted

A graph is a set of nodes (points) joined by edges (lines). An undirected edge works both ways, (0)—(1). A directed edge is one-way, (0)→(1). A weighted edge carries a number, (0)—5—(1).

This problem is interesting because the grid looks undirected, but the water rule makes it directed: water can go from height 5 to height 3, but not from 3 back up to 5. Between equal heights it can go both ways.

(5)→(3)        downhill: water flows 5 → 3, never 3 → 5
(4)⇄(4)        equal heights: both ways

Three ways a graph can be given, and building an adjacency list

n = 3
edges = [[0, 1], [1, 2]]       # 0 -> 1, 1 -> 2
adj = [[] for _ in range(n)]
for u, v in edges:
    adj[u].append(v)           # directed: one way only
print(adj)                     # [[1], [2], []]

Visited, connected components, BFS, DFS

The visited mark stops a walk from going round in circles (with equal heights, water could bounce 4 → 4 → 4… forever). A connected component is a group of nodes that can reach each other. BFS spreads level by level with a queue (collections.deque). DFS goes as deep as it can with recursion, then backs up. Both reach exactly the same set of cells from a start, so for "mark everything reachable" either one works.

A grid is a graph

Each cell (r, c) is a node; its neighbours are up, down, left, right, which the problem calls north, south, west, east. The 4 moves live in a list of (dr, dc) pairs. Always do the bounds check before reading a neighbour.

             north (-1, 0)
west (0,-1) ←  (r, c)  → east (0, +1)
             south (+1, 0)

heights = [[1, 2],
           [3, 4]]
rows, cols = len(heights), len(heights[0])
r, c = 0, 1
found = []
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:
        found.append((nr, nc))
print(found)                   # [(1, 1), (0, 0)]

Multi-start traversal

Here we don't start from one cell; we start from every border cell of an ocean, all sharing one visited grid. A cell already marked by an earlier start is never explored again. That sharing is what keeps the total work small (see Part B ⑨).

Part A · Brute force: follow the water from every cell

LeetCode 417 · Pacific Atlantic Water Flow

1The question in simple words

An m × n island is split into square cells; heights[r][c] is the height of each cell. The Pacific touches the top and left edges. The Atlantic touches the bottom and right edges. Rain on a cell can flow to a north/south/east/west neighbour whose height is less than or equal to the current height, and from any cell next to an ocean straight into that ocean. Return every [r, c] whose water can reach both oceans.

            Pacific  ~  ~  ~  ~  ~
          ~   1   2   2   3  (5)  *
          ~   3   2   3  (4) (4)  *
Pacific   ~   2   4  (5)  3   1   *   Atlantic
          ~  (6) (7)  1   4   5   *
          ~  (5)  1   1   2   4   *
              *   *   *   *   *
                   Atlantic
( ) = the 7 answer cells

Answer: [[0,4],[1,3],[1,4],[2,2],[3,0],[3,1],[4,0]].

The teacher's two example cells

• The 4 at (2,1). Its left neighbour is 2 and the cell above is 2: lower, so water runs left and up, straight to the Pacific. But below is 7 and right is 5: higher, water can't go there. Can it get to the Atlantic some other way? No. So (2,1) is not in the answer.
• The 5 at (2,2). Up is 3 (lower), then that 3 → 3 at (1,2)… keeps going to the top/left: Pacific ✓. Right is 3, then 1 at (2,4), which touches the right edge: Atlantic ✓. (Down is 1 too.) Both oceans, so (2,2) is in the answer.

to Pacific:   5(2,2) → 3(1,2) → 2(1,1) → 2(0,1) → top edge
to Atlantic:  5(2,2) → 3(2,3) → 1(2,4) → right edge

2What the constraints tell us

• 1 ≤ m, n ≤ 200 → at most 40,000 cells. The grid is never empty.
• Heights are 0 to 10⁵; we only compare them, so size doesn't matter.
• If we do a full search from every cell, that's up to 40,000 × 40,000 = 1.6 × 10⁹ steps. Way over the rough 10⁸ limit. So the brute force will be too slow on big grids. We still write it, because it's the natural first idea and a great checker.

3Intuition

Drop a bucket of water on a cell and watch where it can run. If some of it reaches the top or left edge, and some of it reaches the bottom or right edge, the cell counts.

4Building the logic

"Where can the water run?" is a traversal: from the cell, step to neighbours with height ≤ current, and keep going. Use a fresh visited set per start, because equal heights let water go back and forth. While walking, note whether we ever stand on a cell in row 0 or column 0 (Pacific side) and in row m−1 or column n−1 (Atlantic side).

5Approach steps

1. For every cell, run a BFS that moves to neighbours with height ≤ current.
2. Track two flags: touched a Pacific edge? touched an Atlantic edge?
3. If both, add the cell to the answer.

6Code (Python)

from collections import deque

class Solution:
    def pacificAtlantic(self, heights):
        m, n = len(heights), len(heights[0])
        res = []
        for i in range(m):
            for j in range(n):
                pac = atl = False
                seen = {(i, j)}
                q = deque([(i, j)])
                while q:
                    r, c = q.popleft()
                    if r == 0 or c == 0:
                        pac = True
                    if r == m - 1 or c == n - 1:
                        atl = True
                    for dr, dc in ((-1, 0), (1, 0), (0, -1), (0, 1)):
                        nr, nc = r + dr, c + dc
                        if (0 <= nr < m and 0 <= nc < n and (nr, nc) not in seen
                                and heights[nr][nc] <= heights[r][c]):   # downhill or flat
                            seen.add((nr, nc))
                            q.append((nr, nc))
                if pac and atl:
                    res.append([i, j])
        return res

7Code line by line

8Dry run

For the 4 at (2,1): the queue visits (2,1) → (1,1)=2, (2,0)=2 → from (1,1): (0,1)=2 → from (0,1): (0,0)=1. Rows/columns touched: row 0 and column 0 → pac = True. Never row 4 or column 4 → atl = False. Not added ✓, as the teacher said.

9Complexity & remember

• Time O((m·n)²): one search of up to m·n cells, for each of m·n cells. Too slow at 200 × 200.
• Space O(m·n) for one search's set and queue.

Part B · Reverse DFS from both borders

1The question

Same question. Goal: O(m·n) instead of O((m·n)²).

2What the constraints tell us

40,000 cells means an O(m·n) idea is instant, and storing a couple of m × n grids (80,000 booleans) is no problem at all.

3Intuition: let the ocean climb uphill

The teacher's observation: water can only enter an ocean through a border cell. Every cell on the top row and left column pours into the Pacific; every cell on the bottom row and right column pours into the Atlantic. So the border cells are where all the successful paths end.

Instead of starting at every cell and hoping to reach the border, start at the border and walk the paths backwards. Walking a downhill path backwards means walking uphill: from a cell, move to a neighbour whose height is greater than or equal to the current one. Every cell this reverse walk reaches can send water down to that border, and so into the ocean.

real flow:     7 → 4 → 2 → (Pacific)     each step goes ≤
reverse walk:  (Pacific) → 2 → 4 → 7     each step goes ≥

4Building the logic from the teacher's walk-through

Why the condition flips to ≥

Say we're standing on a border 2 and look at a neighbour 3. Could water from that 3 come to us? Yes, 3 → 2 is downhill. So the 3 can reach this ocean: mark it. Now say the neighbour is a 1. Could water from 1 climb to our 2? No. Don't mark it from here. So in the reverse walk: go to a neighbour only if its height ≥ the current height. Equal counts too, because flow between equal heights is allowed.

Why one visited grid is not enough: one per ocean

A cell isn't just "visited or not". We need to know which ocean's walk reached it. A cell reached by both walks is an answer. So each cell needs two pieces of information. The teacher's two options: store a pair (Pacific, Atlantic) in every cell, or make two boolean grids the same size as heights: pac and atl. Both cost 2 × m × n. She goes with two grids.

Which border fills which grid

Skip a border cell that is already marked

In her walk-through, when she moves on to the next border cell and finds it already true, she does not start again from it: an earlier walk already got there and therefore already explored everything reachable from it. Starting again would redo that work.

The final pass

After all four border loops, walk every cell: if pac[i][j] and atl[i][j] are both True, add [i, j] to the answer.

5Approach steps

1. Make pac and atl, two m × n grids of False.
2. For each row i: DFS from (i, 0) into pac, and from (i, n−1) into atl.
3. For each column j: DFS from (0, j) into pac, and from (m−1, j) into atl.
4. DFS(r, c, grid): mark the cell; for each in-bounds, unmarked neighbour with height ≥ current, recurse.
5. Collect every cell that is True in both grids.

6Code (Python)

import sys

class Solution:
    def pacificAtlantic(self, heights):
        sys.setrecursionlimit(100000)
        m, n = len(heights), len(heights[0])
        pac = [[False] * n for _ in range(m)]
        atl = [[False] * n for _ in range(m)]

        def dfs(r, c, seen):
            seen[r][c] = True
            for dr, dc in ((-1, 0), (1, 0), (0, -1), (0, 1)):
                nr, nc = r + dr, c + dc
                if nr < 0 or nr >= m or nc < 0 or nc >= n:
                    continue                          # off the island
                if seen[nr][nc]:
                    continue                          # already reached by this ocean
                if heights[nr][nc] < heights[r][c]:
                    continue                          # lower: water can't climb to us
                dfs(nr, nc, seen)

        for i in range(m):
            if not pac[i][0]:
                dfs(i, 0, pac)                        # first column -> Pacific
            if not atl[i][n - 1]:
                dfs(i, n - 1, atl)                    # last column -> Atlantic
        for j in range(n):
            if not pac[0][j]:
                dfs(0, j, pac)                        # first row -> Pacific
            if not atl[m - 1][j]:
                dfs(m - 1, j, atl)                    # last row -> Atlantic

        res = []
        for i in range(m):
            for j in range(n):
                if pac[i][j] and atl[i][j]:
                    res.append([i, j])
        return res

7Code line by line

8Dry run

The LeetCode grid. Loop order: for each row i, first the Pacific start (i, 0), then the Atlantic start (i, 4); then the same for each column. Neighbour order: up, down, left, right.

     c0 c1 c2 c3 c4
r0    1  2  2  3  5
r1    3  2  3  4  4
r2    2  4  5  3  1
r3    6  7  1  4  5
r4    5  1  1  2  4

The Pacific walk (fills pac)

The Atlantic walk (fills atl)

P P P P P
P P P P P
P P P . .
P P . . .
P . . . .

. . . . A
. . . A A
. . A A A
A A A A A
A A A A A

. . . . ✓
. . . ✓ ✓
. . ✓ . .
✓ ✓ . . .
✓ . . . .

Result: [[0,4],[1,3],[1,4],[2,2],[3,0],[3,1],[4,0]] ✓. Note (2,1), the teacher's 4, is P but not A, as she predicted.

9Complexity & remember

The worry the teacher clears up: a single DFS from the first border cell might cover the whole grid (m·n). There are about m + n border starts. Is it m·n per start, around n³ in total? No. Once a cell is marked in pac, no later Pacific walk enters it again, and we don't even start from marked border cells. If the first start marks a big area, the next start can only mark what's left, and so on. All the Pacific starts together mark each cell at most once: m·n.

• Time O(m·n): m·n for the Pacific walks + m·n for the Atlantic walks (they don't share marks) + m·n for the final pass = 3·m·n.
• Space O(m·n): two grids = 2·m·n, plus the recursion stack. Constants drop.

Part C · The same thing with BFS

The teacher says the only job left after the reversal is "start from these cells and mark everything reachable", so DFS or BFS, whichever feels easier. Steps ①–④ are the same as Part B. What changes:

• Instead of one DFS per border cell, we can put all the Pacific border cells into one queue at the start (a multi-source BFS), mark them, and let the queue spread. Same for the Atlantic.
• The rule for stepping is identical: in bounds, not yet marked, height ≥ current.
• No recursion, so no recursion limit to worry about.

5Approach steps

1. Pacific starts: every cell of row 0 and column 0. Atlantic starts: every cell of row m−1 and column n−1.
2. For each ocean: mark all its starts, put them in a deque, BFS uphill.
3. Return the cells marked by both.

6Code (Python)

from collections import deque

class Solution:
    def pacificAtlantic(self, heights):
        m, n = len(heights), len(heights[0])

        def bfs(starts):
            seen = [[False] * n for _ in range(m)]
            q = deque()
            for r, c in starts:
                if not seen[r][c]:
                    seen[r][c] = True
                    q.append((r, c))
            while q:
                r, c = q.popleft()
                for dr, dc in ((-1, 0), (1, 0), (0, -1), (0, 1)):
                    nr, nc = r + dr, c + dc
                    if (0 <= nr < m and 0 <= nc < n and not seen[nr][nc]
                            and heights[nr][nc] >= heights[r][c]):
                        seen[nr][nc] = True
                        q.append((nr, nc))
            return seen

        pac = bfs([(0, j) for j in range(n)] + [(i, 0) for i in range(m)])
        atl = bfs([(m - 1, j) for j in range(n)] + [(i, n - 1) for i in range(m)])
        return [[i, j] for i in range(m) for j in range(n) if pac[i][j] and atl[i][j]]

7Code line by line

8Dry run (Atlantic, first two rounds)

9Complexity & remember

• Time O(m·n), space O(m·n): same as Part B.

Part D · Revision page

h = [[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]]
print(sorted(Solution().pacificAtlantic(h)))      # [[0, 4], [1, 3], [1, 4], [2, 2], [3, 0], [3, 1], [4, 0]]
print(Solution().pacificAtlantic([[1]]))          # [[0, 0]]
print(sorted(Solution().pacificAtlantic([[2, 1], [1, 2]])))   # [[0, 0], [0, 1], [1, 0], [1, 1]]
print(sorted(Solution().pacificAtlantic([[3, 3, 3], [3, 1, 3], [3, 3, 3]])))   # [[0, 0], [0, 1], [0, 2], [1, 0], [1, 2], [2, 0], [2, 1], [2, 2]]

Based on this video: Pacific Atlantic Water Flow | Graph | Pattern-wise DSA sheet