Pacific Atlantic Water Flow Problem Solution

The Pacific Atlantic Water Flow problem requires identifying cells in a grid where rainwater can flow to both the Pacific and Atlantic oceans. This classic graph traversal problem demonstrates the importance of reverse thinking in algorithm design.

1. Problem Restatement

Clarifying questions to ask the interviewer:

1. What are the constraints on the input dimensions? (e.g., m × n where 1 ≤ m, n ≤ 200)
2. Are duplicate values allowed in the grid?
3. What format should the output be in? (List of coordinates, 2D boolean array, etc.)
4. Can we modify the input grid in-place?
5. What is the expected time complexity target? (e.g., O(mn) or better)

Restatement in my own words: Given a 2D grid representing heights of cells on a continent, determine which cells allow water to flow to both the Pacific Ocean (left and top edges) and Atlantic Ocean (right and bottom edges). Water flows from a cell to adjacent cells with equal or lower height, and we want to find all cells that can reach both oceans.

Problem details:

• Input: An m × n 2D grid of integers representing elevations
• Output: A list of coordinates where water can flow to both oceans
• Flow rule: Water flows to adjacent cells (up, down, left, right) with height ≤ current cell height
• Ocean boundaries:
  • Pacific: Leftmost column and top row
  • Atlantic: Rightmost column and bottom row

Assumptions I'm making:

• Grid is rectangular (m × n dimensions)
• All heights are non-negative integers
• Water can flow to adjacent cells with equal or lower elevation
• We only care about cells that can reach BOTH oceans, not just one

Data shape and hidden structure: The problem has a reverse flow perspective - instead of simulating water flowing from cells to oceans, we can think about which cells can be reached by starting from ocean edges and flowing uphill (in reverse). This creates a graph traversal problem where each cell is a node and edges exist between adjacent cells with valid elevation flow.

The key insight is that we can use BFS/DFS from ocean boundaries to find all reachable cells, then take the intersection of both sets.

2. Pattern Recognition

The problem exhibits the "Reverse BFS/DFS" pattern, where instead of starting from sources and flowing to sinks, we work backwards from the ocean boundaries.

Key signals in the wording:

• "Water can only flow in four directions (up, down, left, or right)"
• "If the rain water can flow to both the Pacific and Atlantic ocean"
• "Return a list of grid coordinates"

Why this fits the pattern: This is fundamentally about finding connected components in a graph where each cell has directional constraints. The key insight is that instead of simulating water flow from every cell outward, we can reverse the logic and simulate "flowing" from ocean boundaries inward. This transforms a complex multi-source flow problem into simpler boundary-based traversal problems.

Core insight: Rather than checking if each cell can reach both oceans (which would require simulating flow from every point), we reverse the problem: we find all cells that can reach the Pacific Ocean and all cells that can reach the Atlantic Ocean. The intersection of these two sets gives us our answer.

The problem's structure suggests a multi-source BFS/DFS approach where we start from the ocean boundaries and expand inward, marking cells that can be reached. The key is recognizing that we're looking for connected components in a directed graph where edges represent valid flow directions.

This pattern is common in grid traversal problems where we need to find reachability from specific boundary conditions, and it's particularly efficient when we can process multiple sources simultaneously.

3. Approach Evolution

My first instinct is to think about this as a graph traversal problem where we need to find cells that can flow to both oceans. But the brute force approach would be inefficient - for each cell, I'd need to simulate water flow to see if it reaches both oceans, which would be O(m²n²) time complexity.

Let me think about this differently. Instead of checking each cell's path to both oceans, I can reverse the thinking - what if I start from the ocean edges and work inward? If I can reach a cell from the Pacific Ocean edge, and also from the Atlantic Ocean edge, then that cell can flow to both oceans.

The key insight is that instead of simulating water flow from every cell, I can simulate reverse flow - starting from ocean edges and finding all cells that can be reached by water flowing backwards. This is much more efficient.

Let me trace through this approach:

1. Start from all cells on the Pacific Ocean boundary (top row and left column)
2. Start from all cells on the Atlantic Ocean boundary (bottom row and right column)
3. Use BFS/DFS to find all cells reachable from each ocean
4. Find the intersection of these two sets

This approach reduces time complexity significantly because:

• Instead of O(m²n²) for brute force, we get O(mn)
• We're essentially doing two separate traversals rather than checking every cell's path
• Each traversal visits each cell at most once

The invariant I need to maintain is that a cell is marked as reachable from an ocean if and only if there exists a path of non-decreasing height values from that ocean edge to the cell.

This is a classic "reverse thinking" pattern where instead of simulating forward flow, we simulate backward reachability. The constraint that water flows to cells with equal or lower height is key - it means we can only move to cells with height ≥ current cell, which makes the reverse traversal valid.

The optimization here is that we're doing two separate graph traversals rather than simulating flow from every single cell. This is a fundamental shift in perspective that reduces the problem space dramatically.

I'll use BFS for consistency and to avoid potential stack overflow with very large grids, though DFS would work equally well with a visited set.

4. Data Structure Choice

For this Pacific Atlantic Water Flow problem, I'll use a combination of data structures to efficiently track which cells can reach each ocean:

Primary Data Structures:

1. Boolean 2D Arrays (pacificReach, atlanticReach) -

   • Used to track which cells can reach the respective oceans
   • Time complexity: O(m×n) for initialization and access
   • Space complexity: O(m×n) for storing reachability status
   • Why needed: Essential for avoiding recomputation and tracking visited states during BFS/DFS

2. Queue (or Stack) for BFS/DFS traversal -

   • Used to process cells in breadth-first or depth-first order
   • Time complexity: O(m×n) for processing all cells at most once
   • Space complexity: O(m×n) in worst case for the queue
   • Why needed: Enables systematic exploration from ocean boundaries

3. List/ArrayList for result storage -

   • Stores final coordinates that can reach both oceans
   • Time complexity: O(m×n) for collecting results
   • Space complexity: O(k) where k is the number of valid cells
   • Why needed: Simple and efficient way to return the final answer

Why These Choices Are Optimal:

The boolean arrays provide O(1) lookup for reachability status, avoiding redundant calculations. The BFS approach with a queue ensures we process cells in the correct order - from ocean boundaries inward, which naturally handles the water flow constraint. Using a queue instead of stack makes the solution more intuitive and ensures we explore cells in order of their distance from the ocean.

The combination allows us to solve this as two separate but related problems (Pacific and Atlantic reachability) while sharing the same underlying data structures for clean implementation.

Helper Structures:

• Direction arrays (int[] dr = {-1, 0, 1, 0} and int[] dc = {0, 1, 0, -1}) -
  • Simplifies neighbor traversal logic
  • Space: O(1) - constant size
  • Time: O(1) for each neighbor access
  • Why needed: Eliminates magic numbers and makes code more maintainable

These structures together provide clean, efficient implementation with clear separation of concerns between tracking reachability, traversal logic, and result collection.

5. Algorithm Walkthrough

Let me trace through the algorithm with a concrete example to show how it works:

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

Step-by-step execution:

1. Initialization:

   • Create pacific and atlantic boolean matrices, all false initially
   • Add border cells to respective queues:
     • Pacific: (0,0), (0,1), (0,2), (0,3), (0,4), (1,0), (2,0), (3,0), (4,0)
     • Atlantic: (4,4), (4,3), (4,2), (4,1), (4,0), (3,4), (2,4), (1,4), (0,4)

2. Pacific BFS Traversal:

   • Start with queue containing all Pacific border cells
   • Process (0,0): height=1, can flow to (0,1) since 2≥1, mark (0,1) as reachable
   • Process (0,1): height=2, can flow to (0,2) since 2≤2, mark (0,2) as reachable
   • Process (0,2): height=2, can flow to (0,3) since 3≥2, mark (0,3) as reachable
   • Process (0,3): height=3, can flow to (0,4) since 5≥3, mark (0,4) as reachable
   • Continue this process, propagating flow inward from the borders

3. Atlantic BFS Traversal:

   • Start with queue containing all Atlantic border cells
   • Process (4,4): height=4, can flow to (4,3) since 5≥4, mark (4,3) as reachable
   • Process (4,3): height=5, can flow to (4,2) since 1≤5, mark (4,2) as reachable
   • Continue propagation inward from the borders

4. Intersection:

   • Find cells where both pacific[i][j] and atlantic[i][j] are true
   • These cells represent locations where water can flow to both oceans

5. Final Result:

   • Return list of coordinates that satisfy the intersection condition
   • For our example: [(0,4), (1,3), (1,4), (2,2), (3,0), (3,1), (4,0)]

The algorithm correctly handles the constraint that water flows to adjacent cells with equal or lower height, and only returns cells that can reach both oceans. The BFS ensures we explore all possible flow paths from the borders efficiently.

The key insight is that instead of checking for each cell whether it can reach both oceans (which would be O(m²n²)), we reverse the thinking: we start from the borders and propagate inward, marking all cells that can be reached from each ocean. This reduces the complexity to O(mn) by avoiding redundant computations.

6. Java Solution

import java.util.*;

public class PacificAtlanticWaterFlow {
    public List<List<Integer>> pacificAtlantic(int[][] heights) {
        if (heights == null || heights.length == 0 || heights[0].length == 0) {
            return new ArrayList<>();
        }
        
        int rows = heights.length;
        int cols = heights[0].length;
        
        // Boolean matrices to track which cells can reach Pacific and Atlantic
        boolean[][] pacific = new boolean[rows][cols];
        boolean[][] atlantic = new boolean[rows][cols];
        
        // BFS from all Pacific border cells (first row and first column)
        Queue<int[]> pacificQueue = new LinkedList<>();
        for (int i = 0; i < rows; i++) {
            pacific[i][0] = true;
            pacificQueue.offer(new int[]{i, 0});
        }
        for (int j = 0; j < cols; j++) {
            pacific[0][j] = true;
            pacificQueue.offer(new int[]{0, j});
        }
        
        // BFS from all Atlantic border cells (last row and last column)
        Queue<int[]> atlanticQueue = new LinkedList<>();
        for (int i = 0; i < rows; i++) {
            atlantic[i][cols - 1] = true;
            atlanticQueue.offer(new int[]{i, cols - 1});
        }
        for (int j = 0; j < cols; j++) {
            atlantic[rows - 1][j] = true;
            atlanticQueue.offer(new int[]{rows - 1, j});
        }
        
        // Process Pacific queue
        bfs(heights, pacificQueue, pacific);
        
        // Process Atlantic queue
        bfs(heights, atlanticQueue, atlantic);
        
        // Collect cells that can reach both oceans
        List<List<Integer>> result = new ArrayList<>();
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if (pacific[i][j] && atlantic[i][j]) {
                    result.add(Arrays.asList(i, j));
                }
            }
        }
        
        return result;
    }
    
    private void bfs(int[][] heights, Queue<int[]> queue, boolean[][] visited) {
        int[][] directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}}; // up, down, left, right
        
        while (!queue.isEmpty()) {
            int[] current = queue.poll();
            int row = current[0];
            int col = current[1];
            
            // Check all four directions
            for (int[] dir : directions) {
                int newRow = row + dir[0];
                int newCol = col + dir[1];
                
                // Skip if out of bounds
                if (newRow < 0 || newRow >= heights.length || 
                    newCol < 0 || newCol >= heights[0].length) {
                    continue;
                }
                
                // Skip if already visited or height condition not met
                if (visited[newRow][newCol] || heights[newRow][newCol] < heights[row][col]) {
                    continue;
                }
                
                visited[newRow][newCol] = true;
                queue.offer(new int[]{newRow, newCol});
            }
        }
    }
}

This solution uses a reverse thinking approach where we start from ocean boundaries and work inward. We perform BFS from all cells adjacent to the Pacific Ocean (top row and left column) and Atlantic Ocean (bottom row and right column), marking cells that can be reached. The intersection of these two sets gives us our answer.

The key insight is that instead of checking if a cell can flow to an ocean, we check if water can flow to a cell from an ocean. This allows us to use BFS efficiently and avoid complex path tracking.

7. Complexity Analysis

Time Complexity: O(m × n)

The algorithm performs a BFS/DFS traversal from all ocean-adjacent cells. Each cell is visited at most once during the traversal from either ocean, and each cell's neighbors are processed exactly once. Since we have m rows and n columns, the total number of operations is bounded by O(m × n).

Space Complexity: O(m × n)

The space complexity comes from:

• The visited boolean matrices (2 × m × n) for tracking which cells can reach each ocean
• The queue used for BFS traversal, which in the worst case can contain all cells (O(m × n))
• The recursion stack for DFS, which in worst case can be O(m × n) deep

Therefore, the overall space complexity is O(m × n).

Why these bounds are correct:

The time complexity is optimal because we must examine each cell at least once to determine if it can reach both oceans. The space complexity is also optimal since we need to store the state of each cell's reachability from both oceans, and in worst-case scenarios (like a flat grid where all cells are reachable), we must maintain information for every cell.

The solution is near-optimal because it avoids redundant traversals by starting from ocean boundaries and working inward, achieving linear time complexity relative to the input size. No better algorithm exists for this problem since we must process every cell at least once to determine reachability conditions.

8. Edge Cases & Pitfalls

Empty and Minimal Inputs

• Empty grid: Handle null or zero-sized arrays gracefully. The solution should return an empty list when there are no cells to process.
• Single cell: A 1×1 grid should work correctly, returning that single cell if it can reach both oceans.
• Single row/column: Grids with only one row or column require careful boundary handling.

Duplicate Values and Repeated States

• Identical heights: Multiple cells with the same elevation can be part of the solution path, so we must not skip them based on height alone.
• Visited state tracking: When using BFS/DFS, we must ensure that a cell isn't added multiple times to the queue or visited set, which could lead to infinite loops or incorrect results.

Boundary Conditions

• Corner cells: Cells at the top-left and bottom-right corners can potentially reach both oceans, so they should be included in the result.
• Edge boundaries: Cells on the edges of the grid (first/last row or column) are critical for determining ocean access and must be handled properly during traversal.

Common Implementation Mistakes

• Wrong direction logic: Misunderstanding that water flows from higher to lower elevations can lead to incorrect traversal. The flow is reverse: we check from ocean edges inward.
• Mutating input: Modifying the original grid during traversal can cause issues or violate constraints if the input is read-only.
• Incorrect queue handling: Not properly managing visited cells or using incorrect data structures (e.g., HashSet instead of boolean[][]) can lead to performance degradation or incorrect results.
• Missing return condition: For grids with no valid cells, the algorithm must return an empty list rather than null or undefined behavior.

// Example edge case handling:
if (heights == null || heights.length == 0 || heights[0].length == 0) {
    return new ArrayList<>();
}

9. Alternative Approaches

There are several alternative approaches to solving the Pacific Atlantic Water Flow problem, each with different trade-offs:

1. Brute Force with DFS from Each Cell Instead of starting from the ocean edges, we could perform a DFS from every cell to determine if water can reach both oceans. For each cell, we'd run two separate DFS traversals - one to check Pacific connectivity and another for Atlantic. This approach would be O(m²n²) time complexity, which is significantly worse than our optimal solution. The main disadvantage is that we're doing redundant work - many cells will be visited multiple times during different traversals.

2. Two-Set Approach with BFS We could use two separate BFS queues to track cells reachable from each ocean. Instead of using a single visited array, we'd maintain two boolean matrices - one for Pacific-reachable cells and another for Atlantic-reachable cells. We'd start BFS from all edge cells and propagate outward, marking cells as reachable to their respective oceans. This approach is functionally equivalent to our solution but uses BFS instead of DFS, which might have different performance characteristics in practice.

3. Single-Visit with Union-Find We could model this as a graph connectivity problem using Union-Find data structure, but this is overkill for the problem. The union-find approach would require building a more complex graph representation and wouldn't provide significant benefits over our direct DFS approach.

4. Backward Flow Approach with Priority Queue Instead of thinking about water flowing forward, we could think about the reverse - starting from ocean levels and "flowing" upward. We'd use a priority queue (min-heap) to process cells in order of increasing height, but this adds unnecessary complexity and doesn't improve the fundamental time complexity.

The approach we chose (DFS from ocean edges) is optimal because it avoids redundant computations by leveraging the fact that water flows from higher to lower elevations, so we can work backwards from the ocean edges rather than forwards from every cell. This is more efficient and cleaner than alternatives that would require multiple traversals or additional data structures for tracking connectivity.

10. Test Cases

public class PacificAtlanticWaterFlow {
    public List<List<Integer>> pacificAtlantic(int[][] heights) {
        // Implementation here
        return new ArrayList<>();
    }
}

Here are representative test cases for the Pacific Atlantic Water Flow problem:

Sample Case 1: Basic 3x3 grid

Input: [[1,2,3],[8,9,4],[7,6,5]]
Expected Output: [[0,2],[1,0],[1,1],[1,2],[2,0],[2,1],[2,2]]

Tricky Case: Grid with flat regions

Input: [[1,1,1],[1,2,1],[1,1,1]]
Expected Output: [[0,0],[0,1],[0,2],[1,0],[1,2],[2,0],[2,1],[2,2]]

Boundary Case: Single row or column

Input: [[1,2,3,4]]
Expected Output: [[0,0],[0,1],[0,2],[0,3]]

Edge Case: Empty grid

Input: []
Expected Output: []

Edge Case: Single element

Input: [[1]]
Expected Output: [[0,0]]

Complex Case: Large variations in elevation

Input: [[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]]
Expected Output: [[0,4],[1,3],[1,4],[2,2],[3,0],[3,1],[4,0]]

These test cases cover various scenarios including regular grids, edge cases with minimal dimensions, flat regions that create multiple valid paths, and complex elevation patterns that require careful handling of the water flow constraints.

11. Final Summary

The core insight is that instead of finding all cells that can flow to both oceans, we reverse the problem by identifying all cells that can reach the Pacific and Atlantic oceans respectively, then finding their intersection. This approach transforms a complex multi-source flow problem into two simpler single-source BFS traversals.

The solution works by starting BFS from all edge cells that touch each ocean and propagating inward to find all reachable cells. The key efficiency comes from recognizing that we only need to traverse each cell once, making the overall complexity linear in terms of the grid size.

This approach is optimal because it leverages the mathematical property that water flows to lower elevations, so we can traverse from ocean edges inward with elevation constraints. The use of two separate boolean matrices ensures we don't double-count cells while maintaining clean separation of the two flow paths.