How to Solve: Pacific Atlantic Water Flow

How to Solve: Pacific Atlantic Water Flow

(Complete Guide for FAANG-Level Interviews)

? Introduction

"This problem tests your ability to model multi-directional constraints—master it, and you’ll crush 1 in 4 graph-based interview questions at FAANG, especially at Google and Meta."

? WHAT YOU NEED TO KNOW FIRST

1. DFS/BFS on grids – Traversing 2D matrices with 4-directional movement (up, down, left, right).
2. Reverse Thinking (Backtracking from boundaries) – Instead of simulating water flow forward, work backward from the oceans.
3. Visited Tracking – Using a 2D boolean array (or bitmask) to mark reachable cells.

? KEY TECHNIQUES & PATTERNS

? STEP-BY-STEP FRAMEWORK

(Repeatable mental checklist for every "Pacific Atlantic" problem)

1. Understand the Problem
2. Water flows from high → low elevation.
3. A cell can flow to the Pacific if it’s on the top/left edge or can reach it via a descending path.
4. A cell can flow to the Atlantic if it’s on the bottom/right edge or can reach it via a descending path.

5. Goal: Find all cells that can flow to both oceans.

6. Model the Grid

7. Represent the grid as a 2D matrix heights[m][n].

8. Define 4-directional movement: (i±1, j) and (i, j±1).

9. Reverse the Problem

10. Instead of checking if water flows from a cell to the ocean, check if water can flow from the ocean to the cell (i.e., the cell is reachable via an ascending path from the ocean).

11. This avoids simulating all possible paths from every cell.

12. Initialize BFS/DFS from Ocean Boundaries

13. Pacific: Start from all cells in the first row and first column.
14. Atlantic: Start from all cells in the last row and last column.

15. Use a queue for BFS or a stack for DFS.

16. Track Reachable Cells

17. Create two m x n boolean matrices:
    • pacific_reachable[i][j] = True if cell (i,j) can flow to the Pacific.
    • atlantic_reachable[i][j] = True if cell (i,j) can flow to the Atlantic.

18. Initialize both with False.

19. Propagate Reachability

20. For each ocean, perform BFS/DFS:
    • If a neighbor (ni, nj) is unvisited and heights[ni][nj] >= heights[i][j] (ascending path), mark it as reachable and enqueue it.

21. Optimization: Skip cells already marked by both oceans.

22. Collect Results

23. Iterate through all cells. If pacific_reachable[i][j] and atlantic_reachable[i][j], add (i,j) to the result.

24. Edge Cases

25. Empty grid → Return [].
26. Single-row or single-column grid → All cells are on the boundary.
27. All cells have the same height → All boundary cells can flow to both oceans.

? WORKED EXAMPLES

Example 1 – Basic (4x4 Grid)

Problem:

[
  [1, 2, 2, 3],
  [3, 2, 3, 4],
  [2, 4, 5, 3],
  [6, 7, 1, 4]
]

Solution: 1. Pacific BFS: Start from (0,0), (0,1), (0,2), (0,3), (1,0), (2,0), (3,0).
- Propagate to cells where heights[ni][nj] >= heights[i][j].
- Mark reachable cells in pacific_reachable. 2. Atlantic BFS: Start from (3,0), (3,1), (3,2), (3,3), (0,3), (1,3), (2,3).
- Propagate similarly. 3. Result: Cells where both matrices are True:
- (0,3), (1,3), (2,2), (3,0), (3,1).

Python Code:

from collections import deque

def pacificAtlantic(heights):

    if not heights or not heights[0]:

        return []


    m, n = len(heights), len(heights[0])

    pacific_reachable = [[False]  n for _ in range(m)]

    atlantic_reachable = [[False]  n for _ in range(m)]


    def bfs(queue, reachable):

        directions = [(1,0), (-1,0), (0,1), (0,-1)]

        while queue:

            i, j = queue.popleft()

            for di, dj in directions:

                ni, nj = i + di, j + dj

                if 0 <= ni < m and 0 <= nj < n and not reachable[ni][nj] and heights[ni][nj] >= heights[i][j]:

                    reachable[ni][nj] = True

                    queue.append((ni, nj))


    # Pacific BFS (top and left edges)

    pacific_queue = deque()

    for i in range(m):

        pacific_queue.append((i, 0))

        pacific_reachable[i][0] = True

    for j in range(n):

        pacific_queue.append((0, j))

        pacific_reachable[0][j] = True

    bfs(pacific_queue, pacific_reachable)


    # Atlantic BFS (bottom and right edges)

    atlantic_queue = deque()

    for i in range(m):

        atlantic_queue.append((i, n-1))

        atlantic_reachable[i][n-1] = True

    for j in range(n):

        atlantic_queue.append((m-1, j))

        atlantic_reachable[m-1][j] = True

    bfs(atlantic_queue, atlantic_reachable)


    # Collect results

    result = []

    for i in range(m):

        for j in range(n):

            if pacific_reachable[i][j] and atlantic_reachable[i][j]:

                result.append([i, j])

    return result

Time Complexity: O(m n) (each cell is visited at most twice). Space Complexity: O(m n) (for the two reachability matrices).

Why This Works: - Reverse BFS ensures we only traverse cells that can flow to the ocean, avoiding exponential path checks. - Multi-source BFS efficiently propagates reachability from all boundary cells simultaneously.

Example 2 – Medium (3x3 Grid with Plateaus)

Problem:

[
  [1, 1, 1],
  [1, 1, 1],
  [1, 1, 1]
]

Solution: - All cells are on the boundary or can flow to both oceans (since all heights are equal). - Result: All 9 cells.

Python Code: (Same as above, but the BFS will mark all cells as reachable.)

Why This Works: - Equal heights allow water to flow in any direction, so all boundary cells propagate reachability to the entire grid.

Example 3 – Hard (Follow-Up: Optimize Space)

Problem: "Can you solve this with O(1) extra space (excluding the result)?" Solution: - Use bitmasking to store reachability in a single integer per cell (e.g., reachable[i][j] = 1 for Pacific, 2 for Atlantic, 3 for both). - Alternatively, modify the input grid in-place (if allowed).

Optimized Python Code:

def pacificAtlantic_optimized(heights):

    if not heights or not heights[0]:

        return []


    m, n = len(heights), len(heights[0])

    reachable = [[0]  n for _ in range(m)]  # 0: unreachable, 1: Pacific, 2: Atlantic, 3: both


    def dfs(i, j, ocean):

        reachable[i][j] |= ocean

        for di, dj in [(1,0), (-1,0), (0,1), (0,-1)]:

            ni, nj = i + di, j + dj

            if 0 <= ni < m and 0 <= nj < n and (reachable[ni][nj] & ocean) == 0 and heights[ni][nj] >= heights[i][j]:

                dfs(ni, nj, ocean)


    # Pacific DFS (top and left edges)

    for i in range(m):

        dfs(i, 0, 1)

    for j in range(n):

        dfs(0, j, 1)


    # Atlantic DFS (bottom and right edges)

    for i in range(m):

        dfs(i, n-1, 2)

    for j in range(n):

        dfs(m-1, j, 2)


    # Collect results

    result = []

    for i in range(m):

        for j in range(n):

            if reachable[i][j] == 3:

                result.append([i, j])

    return result

Time Complexity: O(m n) (same as BFS). Space Complexity: O(m n) (but uses a single matrix instead of two).

Why This Works: - Bitmasking reduces space by combining two boolean matrices into one integer matrix. - DFS is used here for simplicity, but BFS would work similarly.

❌ Common Mistakes

? INTERVIEW TrapS

? 1-Minute Recap (Closing Script)

"Here’s your 60-second cheat sheet for Pacific Atlantic Water Flow: 1. Reverse the problem: Instead of checking if water flows from a cell to the ocean, check if the ocean can reach the cell via an ascending path. 2. Multi-source BFS/DFS: Start from all Pacific (top/left) and Atlantic (bottom/right) boundary cells. 3. Track reachability: Use two matrices (or bitmasking) to mark cells that can flow to each ocean. 4. Collect results: Cells marked in both matrices are your answer. 5. Edge cases: Handle empty grids, single-row/column grids, and equal heights. This approach is optimal—O(mn) time and space—and demonstrates your ability to model constraints efficiently. Now go crush that interview!

? Final Notes

• Practice Variations: Try solving with DFS instead of BFS, or with diagonal movement.
• Whiteboard Tip: Draw the grid and annotate reachable cells as you walk through the BFS.
• Time Management: Spend 5-10 minutes on the initial solution, then 5 minutes optimizing if asked.

This framework is directly usable in an interview—no fluff, just actionable steps. Good luck! ?