Problem Description

You're given an m x n matrix representing an island where each cell contains a height value. The island is surrounded by two oceans:

• Pacific Ocean: touches the left and top edges of the island
• Atlantic Ocean: touches the right and bottom edges of the island

When it rains on the island, water flows from each cell to neighboring cells (north, south, east, west) if the neighboring cell's height is less than or equal to the current cell's height. Water that reaches cells adjacent to an ocean flows into that ocean.

Your task is to find all cells from which rainwater can flow to both the Pacific Ocean AND the Atlantic Ocean. Return these cells as a list of coordinates [r, c].

Key Points:

• Water flows from higher or equal height to lower or equal height cells
• Water can move in 4 directions: up, down, left, right
• A cell must be able to reach both oceans (not just one) to be included in the result
• Cells on the edges are directly adjacent to their respective oceans

Example visualization: If we have a 5×5 island, the Pacific Ocean borders are at row 0 and column 0, while the Atlantic Ocean borders are at row 4 and column 4. Water from a cell in the middle needs to find paths to both ocean boundaries following the height rules.

Flowchart Walkthrough

First, let's pin down the algorithm using the Flowchart. Here's a step-by-step walkthrough:

Is it a graph?

• Yes: The problem involves a grid where each cell can be connected to its neighbors (up, down, left, right). Water flows between cells based on height relationships, creating edges between nodes (cells). This is essentially a graph traversal problem.

Is it a tree?

• No: The grid structure with multiple possible paths and potential cycles (water can flow in circles if heights allow) means this is not a tree structure.

Is the problem related to directed acyclic graphs?

• No: While water flow creates directed edges (from higher/equal to lower/equal heights), the problem isn't about DAG properties like topological ordering. We need to find cells that can reach both oceans.

Is the problem related to shortest paths?

• No: We don't need to find the shortest path to the oceans. We only need to determine if water can reach both oceans from a given cell, regardless of path length.

Does the problem involve connectivity?

• Yes: The core of the problem is about connectivity - determining which cells are connected to both the Pacific and Atlantic oceans through valid water flow paths.

Does the problem have small constraints?

• Yes: The constraints are typically manageable (m × n grid with reasonable dimensions), allowing for traversal-based approaches.

DFS/backtracking?

• Yes: DFS is perfect for exploring all possible flow paths from ocean boundaries inward, marking all reachable cells.

Conclusion: The flowchart suggests using DFS (Depth-First Search) to solve this problem. The solution uses DFS (implemented as BFS in the provided code) to traverse from ocean boundaries inward, finding all cells reachable from each ocean, then returning the intersection of these two sets.

Intuition

The key insight is to reverse our thinking. Instead of checking if water from each cell can reach both oceans (which would be inefficient), we ask: "Which cells can be reached FROM each ocean?"

Think about it this way: if water can flow from cell A to the ocean, then we can also trace backwards from the ocean to cell A by going uphill or staying at the same level. This reverse approach is much more efficient.

Here's the thought process:

1. Start from the ocean boundaries: We know cells touching the Pacific (top/left edges) can definitely reach the Pacific. Similarly, cells touching the Atlantic (bottom/right edges) can reach the Atlantic.

2. Flow backwards: From these boundary cells, we can "flow uphill" - moving to neighboring cells with heights greater than or equal to the current cell. This simulates the reverse of water flowing downhill.

3. Mark reachable cells: As we traverse from each ocean, we mark all cells that can be reached. This gives us two sets:

   • Set 1: All cells that can reach the Pacific Ocean
   • Set 2: All cells that can reach the Atlantic Ocean

4. Find the intersection: The answer is simply the cells that appear in both sets - these are the cells from which water can flow to both oceans.

Why is this approach better? Instead of doing a traversal from each of the m × n cells to check if they can reach both oceans (which would be O(m × n × (m + n))), we only do two traversals starting from the ocean boundaries. This reduces our complexity significantly.

The beauty of this solution lies in recognizing that water flow is reversible in terms of reachability - if water can flow from A to B (going downhill), then we can trace from B to A (going uphill).

Solution Approach

The implementation uses BFS (Breadth-First Search) to execute our reverse-flow strategy. Here's how the solution works:

1. Initialize Data Structures:

• Two sets vis1 and vis2 to track cells reachable from Pacific and Atlantic oceans respectively
• Two queues q1 and q2 for BFS traversal from each ocean
• Variables m and n store the dimensions of the grid

2. Identify Ocean Boundaries:

for i in range(m):
    for j in range(n):
        if i == 0 or j == 0:  # Pacific Ocean (top and left edges)
            vis1.add((i, j))
            q1.append((i, j))
        if i == m - 1 or j == n - 1:  # Atlantic Ocean (bottom and right edges)
            vis2.add((i, j))
            q2.append((i, j))

• Cells on row 0 or column 0 touch the Pacific Ocean
• Cells on row m-1 or column n-1 touch the Atlantic Ocean
• These boundary cells are added to their respective queues and marked as visited

3. BFS Traversal Function:

def bfs(q, vis):
    while q:
        for _ in range(len(q)):
            i, j = q.popleft()
            for a, b in [[0, -1], [0, 1], [1, 0], [-1, 0]]:  # 4 directions
                x, y = i + a, j + b
                if (0 <= x < m and 0 <= y < n and 
                    (x, y) not in vis and 
                    heights[x][y] >= heights[i][j]):  # Can flow "uphill"
                    vis.add((x, y))
                    q.append((x, y))

• For each cell in the queue, check all 4 neighboring cells
• The key condition: heights[x][y] >= heights[i][j] - we can move to cells with equal or greater height (reverse flow)
• If a valid unvisited cell is found, mark it as visited and add to queue

4. Execute BFS from Both Oceans:

bfs(q1, vis1)  # Find all cells reachable from Pacific
bfs(q2, vis2)  # Find all cells reachable from Atlantic

5. Find Intersection:

return [(i, j) for i in range(m) for j in range(n) 
        if (i, j) in vis1 and (i, j) in vis2]

• Return cells that exist in both vis1 and vis2
• These are the cells from which water can flow to both oceans

Time Complexity: O(m × n) - Each cell is visited at most twice (once from each ocean)

Space Complexity: O(m × n) - For the visited sets and queues in worst case

The algorithm elegantly solves the problem by reversing the flow direction and using set intersection to find cells connected to both oceans.

Example Walkthrough

Let's walk through a small 3×3 example to illustrate the solution approach:

heights = [[3, 3, 5],
           [3, 1, 3],
           [0, 2, 4]]

Step 1: Identify Ocean Boundaries

Pacific Ocean touches:

• Top row: (0,0), (0,1), (0,2)
• Left column: (0,0), (1,0), (2,0)

Atlantic Ocean touches:

• Bottom row: (2,0), (2,1), (2,2)
• Right column: (0,2), (1,2), (2,2)

Initial state:

• vis1 (Pacific): {(0,0), (0,1), (0,2), (1,0), (2,0)}
• vis2 (Atlantic): {(2,0), (2,1), (2,2), (0,2), (1,2)}

Step 2: BFS from Pacific Ocean (reverse flow - going uphill)

Starting from Pacific boundaries, we can reach cells with height ≥ current:

From (0,0) with height 3:

• Check (1,0): height 3 ≥ 3 ✓ (already in vis1)
• Check (0,1): height 3 ≥ 3 ✓ (already in vis1)

From (0,1) with height 3:

• Check (1,1): height 1 < 3 ✗ (can't go there)

From (0,2) with height 5:

• Check (1,2): height 3 < 5 ✗ (can't go there)

From (1,0) with height 3:

• Check (1,1): height 1 < 3 ✗ (can't go there)

From (2,0) with height 0:

• Check (2,1): height 2 ≥ 0 ✓ (add to vis1)

After processing (2,1) with height 2:

• Check (1,1): height 1 < 2 ✗ (can't go there)
• Check (2,2): height 4 ≥ 2 ✓ (add to vis1)

Final vis1: {(0,0), (0,1), (0,2), (1,0), (2,0), (2,1), (2,2)}

Step 3: BFS from Atlantic Ocean (reverse flow - going uphill)

Starting from Atlantic boundaries:

From (2,2) with height 4:

• Check (2,1): height 2 < 4 ✗ (can't go there)
• Check (1,2): height 3 < 4 ✗ (can't go there)

From (0,2) with height 5:

• Check (0,1): height 3 < 5 ✗ (can't go there)
• Check (1,2): height 3 < 5 ✗ (can't go there)

From (2,0) with height 0:

• Check (1,0): height 3 ≥ 0 ✓ (add to vis2)

From (1,0) with height 3:

• Check (0,0): height 3 ≥ 3 ✓ (add to vis2)

From (0,0) with height 3:

• Check (0,1): height 3 ≥ 3 ✓ (add to vis2)

Final vis2: {(2,0), (2,1), (2,2), (0,2), (1,2), (1,0), (0,0), (0,1)}

Step 4: Find Intersection

Cells in both vis1 AND vis2:

• (0,0) ✓ in both
• (0,1) ✓ in both
• (0,2) ✓ in both
• (1,0) ✓ in both
• (2,0) ✓ in both
• (2,1) ✓ in both
• (2,2) ✓ in both

Result: [[0,0], [0,1], [0,2], [1,0], [2,0], [2,1], [2,2]]

These are all the cells from which water can flow to both oceans. Notice that (1,1) with height 1 is surrounded by higher cells, creating a "valley" that prevents water from reaching either ocean, and (1,2) can only reach the Atlantic but not the Pacific.

Solution Implementation

Time and Space Complexity

Time Complexity: O(m * n) where m is the number of rows and n is the number of columns in the heights matrix.

• The initial setup iterates through all cells once to identify border cells: O(m * n)
• The BFS from Pacific ocean borders visits each reachable cell at most once: O(m * n)
• The BFS from Atlantic ocean borders visits each reachable cell at most once: O(m * n)
• The final iteration to find cells in both sets: O(m * n)
• Total: O(m * n) + O(m * n) + O(m * n) + O(m * n) = O(m * n)

Space Complexity: O(m * n)

• vis1 set can contain at most all cells: O(m * n)
• vis2 set can contain at most all cells: O(m * n)
• q1 queue can contain at most all cells during BFS: O(m * n)
• q2 queue can contain at most all cells during BFS: O(m * n)
• The result list can contain at most all cells: O(m * n)
• Total: O(m * n) (since these are not all used simultaneously at maximum capacity, the overall space complexity remains O(m * n))

Common Pitfalls

1. Incorrect Flow Direction Logic

One of the most common mistakes is misunderstanding the flow direction when implementing the reverse-flow approach. Students often write:

Incorrect:

# Wrong: checking if we can flow "downhill" in reverse traversal
if heights[next_row][next_col] <= heights[curr_row][curr_col]:
    visited.add((next_row, next_col))

Correct:

# Right: we need to go "uphill" when traversing backwards from ocean
if heights[next_row][next_col] >= heights[curr_row][curr_col]:
    visited.add((next_row, next_col))

Why this matters: Since we're traversing backwards from the ocean, we need to move to cells with equal or greater height. Think of it as asking "which cells could have sent water to the current cell?" - only cells with height ≥ current cell's height.

2. Using Lists Instead of Sets for Visited Tracking

Using lists for the visited data structure severely impacts performance:

Inefficient:

pacific_visited = []  # O(n) lookup time
atlantic_visited = []

# Checking membership becomes O(n)
if [next_row, next_col] not in pacific_visited:
    pacific_visited.append([next_row, next_col])

Efficient:

pacific_visited = set()  # O(1) lookup time
atlantic_visited = set()

# Checking membership is O(1)
if (next_row, next_col) not in pacific_visited:
    pacific_visited.add((next_row, next_col))

3. Forgetting to Handle Equal Heights

A critical oversight is not allowing water to flow between cells of equal height:

Wrong:

# Only allows strictly greater heights
if heights[next_row][next_col] > heights[curr_row][curr_col]:

Correct:

# Allows equal or greater heights
if heights[next_row][next_col] >= heights[curr_row][curr_col]:

Water can flow horizontally across cells of the same height, which is essential for finding all valid paths.

4. Incorrect Ocean Boundary Identification

Mixing up which edges belong to which ocean:

Common Mistake:

# Wrong assignment of oceans
if row == 0 or col == cols - 1:  # Mixing top with right edge
    pacific_visited.add((row, col))

Correct:

# Pacific: top (row=0) and left (col=0)
if row == 0 or col == 0:
    pacific_visited.add((row, col))

# Atlantic: bottom (row=rows-1) and right (col=cols-1)  
if row == rows - 1 or col == cols - 1:
    atlantic_visited.add((row, col))

5. Not Processing All Cells at Current BFS Level

Forgetting to process all cells at the current level before moving to the next can lead to incorrect traversal:

Problematic:

while queue:
    curr_row, curr_col = queue.popleft()
    # Immediately processing without level separation
    for delta_row, delta_col in directions:
        # ...

Better (though both work for this problem):

while queue:
    level_size = len(queue)
    for _ in range(level_size):
        curr_row, curr_col = queue.popleft()
        # Process all cells at current distance from ocean

While both approaches find the correct cells, level-by-level processing is clearer and helps if you need to track distance from oceans.