Introduction

Pacific Atlantic Water Flow is one of the most important Matrix DFS and BFS interview problems.

You are given:

 heights[][]

Goal:

Find cells from which water can reach both oceans.

Rules:

Pacific → Top + LeftAtlantic → Bottom + Right

Water flows:

Higher → Lower or Equal

Example

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

Key Observation

Instead of starting from:

Every Cell

Start from:

Ocean Boundaries

Run DFS/BFS from:

Pacific Border and Atlantic Border

Then find:

Intersection

Algorithm

1. Traverse Pacific borders.2. Traverse Atlantic borders.
3. Mark reachable cells.
4. Find common cells.
5. Return answer.

Dry Run

Pacific Reachable:

Top + Left

Atlantic Reachable:

Top + Left

Answer:

Cells present in both sets.

Approach : DFS

Explanation

  1. Start from ocean borders.
  2. Move to greater or equal heights.
  3. Mark visited cells.
  4. Find intersection.

Practice

Complexity Analysis

DFSTime Complexity: O(m × n)
Space Complexity: O(m × n)

BFS
Time Complexity: O(m × n)
Space Complexity: O(m × n)

Why This Problem is Important

  • BFS
  • DFS
  • Matrix Traversal
  • Multi Source Traversal
  • Graph Reachability

Common Beginner Mistakes

  • Starting DFS from every cell
  • Wrong flow direction
  • Missing intersection logic
  • Boundary traversal mistakes
  • Revisiting cells

Interview Tip

Always explain:

Start from oceans not from cells.

This reduces complexity dramatically.

Related Questions

  • Number of Islands
  • Flood Fill
  • Surrounded Regions
  • Rotting Oranges
  • Walls and Gates

Final Takeaway

Pacific Atlantic Water Flow is a classic multi-source DFS/BFS problem.

It teaches:

  • Multi Source Traversal
  • Reachability
  • Matrix DFS
  • Matrix BFS

Mastering Pacific Atlantic Water Flow makes advanced graph traversal problems significantly easier.