LeetCode 417 Pacific Atlantic Water Flow - DFS and BFS Solutions(Med, Java, O(mn))

Problem Overview

• LeetCode 417 Pacific Atlantic Water Flow

Given an m x n matrix representing island heights, water can flow from a cell to adjacent cells with equal or lower height. Find all cells where water can flow to both Pacific Ocean (top/left edges) and Atlantic Ocean (bottom/right edges).

Key Insight: Reverse Thinking

Instead of checking "can water flow FROM this cell to both oceans?", we ask: "Which cells can water flow TO from each ocean?"

• Start from ocean edges and work inward
• Use DFS/BFS to find all reachable cells from each ocean
• Return intersection of both sets

Solution 1: DFS Approach

class Solution {
    private int[][] heights;
    private int m, n;
    private int[][] directions = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};

    public List<List<Integer>> pacificAtlantic(int[][] heights) {
        this.heights = heights;
        this.m = heights.length;
        this.n = heights[0].length;

        // Track cells reachable from each ocean
        boolean[][] pacificReachable = new boolean[m][n];
        boolean[][] atlanticReachable = new boolean[m][n];

        // Start DFS from Pacific edges (top row, left column)
        for (int i = 0; i < m; i++) {
            dfs(i, 0, pacificReachable, Integer.MIN_VALUE);
        }
        for (int j = 0; j < n; j++) {
            dfs(0, j, pacificReachable, Integer.MIN_VALUE);
        }

        // Start DFS from Atlantic edges (bottom row, right column)
        for (int i = 0; i < m; i++) {
            dfs(i, n - 1, atlanticReachable, Integer.MIN_VALUE);
        }
        for (int j = 0; j < n; j++) {
            dfs(m - 1, j, atlanticReachable, Integer.MIN_VALUE);
        }

        // Find intersection - cells reachable from both oceans
        List<List<Integer>> result = new ArrayList<>();
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (pacificReachable[i][j] && atlanticReachable[i][j]) {
                    result.add(Arrays.asList(i, j));
                }
            }
        }

        return result;
    }

    private void dfs(int row, int col, boolean[][] reachable, int prevHeight) {
        // Boundary check and visited check
        if (row < 0 || row >= m || col < 0 || col >= n || 
            reachable[row][col] || heights[row][col] < prevHeight) {
            return;
        }

        // Mark as reachable
        reachable[row][col] = true;

        // Explore all 4 directions
        for (int[] dir : directions) {
            dfs(row + dir[0], col + dir[1], reachable, heights[row][col]);
        }
    }
}

DFS Explanation

Key Points:

1. Reverse Flow: Start from ocean edges, flow to higher/equal cells
2. Base Cases: Out of bounds, already visited, or height too low
3. Recursive Exploration: Visit all 4 directions from current cell
4. Height Condition: heights[row][col] >= prevHeight (water flows upward from ocean)

Why it works:

• If water can flow from ocean edge to cell (i,j), then water from (i,j) can flow to that ocean
• DFS naturally explores all connected components reachable from starting points

Solution 2: BFS Approach

class Solution {
    private int[][] directions = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};

    public List<List<Integer>> pacificAtlantic(int[][] heights) {
        int m = heights.length, n = heights[0].length;

        // Track cells reachable from each ocean
        boolean[][] pacificReachable = new boolean[m][n];
        boolean[][] atlanticReachable = new boolean[m][n];

        // Initialize queues with ocean border cells
        Queue<int[]> pacificQueue = new LinkedList<>();
        Queue<int[]> atlanticQueue = new LinkedList<>();

        // Add Pacific border cells (top row and left column)
        for (int i = 0; i < m; i++) {
            pacificQueue.offer(new int[]{i, 0});
            pacificReachable[i][0] = true;
        }
        for (int j = 1; j < n; j++) { // j=1 to avoid duplicate corner
            pacificQueue.offer(new int[]{0, j});
            pacificReachable[0][j] = true;
        }

        // Add Atlantic border cells (bottom row and right column)
        for (int i = 0; i < m; i++) {
            atlanticQueue.offer(new int[]{i, n - 1});
            atlanticReachable[i][n - 1] = true;
        }
        for (int j = 0; j < n - 1; j++) { // j < n-1 to avoid duplicate corner
            atlanticQueue.offer(new int[]{m - 1, j});
            atlanticReachable[m - 1][j] = true;
        }

        // Perform BFS from each ocean
        bfs(heights, pacificQueue, pacificReachable);
        bfs(heights, atlanticQueue, atlanticReachable);

        // Find intersection
        List<List<Integer>> result = new ArrayList<>();
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (pacificReachable[i][j] && atlanticReachable[i][j]) {
                    result.add(Arrays.asList(i, j));
                }
            }
        }

        return result;
    }

    private void bfs(int[][] heights, Queue<int[]> queue, boolean[][] reachable) {
        int m = heights.length, n = heights[0].length;

        while (!queue.isEmpty()) {
            int[] current = queue.poll();
            int row = current[0], col = current[1];

            // Explore all 4 directions
            for (int[] dir : directions) {
                int newRow = row + dir[0];
                int newCol = col + dir[1];

                // Check bounds, visited status, and height condition
                if (newRow >= 0 && newRow < m && newCol >= 0 && newCol < n &&
                    !reachable[newRow][newCol] && 
                    heights[newRow][newCol] >= heights[row][col]) {

                    reachable[newRow][newCol] = true;
                    queue.offer(new int[]{newRow, newCol});
                }
            }
        }
    }
}

BFS Explanation

Key Points:

1. Level-by-level exploration: Process all cells at distance k before distance k+1
2. Queue initialization: Start with all border cells for each ocean
3. Height condition: Only move to cells with height >= currentHeight
4. Avoid duplicates: Careful indexing when adding border cells

BFS vs DFS differences:

• BFS: Uses queue, processes by distance from ocean
• DFS: Uses recursion stack, may go deep before exploring neighbors
• Performance: Similar time complexity, BFS might have better cache locality

Detailed Example Walkthrough

For matrix:

[[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 1: Pacific Ocean DFS/BFS

Starting from edges (row 0, col 0):

Pacific reachable:
[[T,T,T,T,F],
 [T,T,T,T,F],
 [T,T,T,F,F],
 [T,T,F,F,F],
 [T,F,F,F,F]]

Step 2: Atlantic Ocean DFS/BFS

Starting from edges (row 4, col 4):

Atlantic reachable:
[[F,F,F,F,T],
 [F,F,F,T,T],
 [F,F,T,T,T],
 [F,T,T,T,T],
 [F,T,T,T,T]]

Step 3: Find Intersection

Pacific AND Atlantic:
[[F,F,F,F,F],
 [F,F,F,T,F],
 [F,F,T,F,F],
 [F,T,F,F,F],
 [F,F,F,F,F]]

Result: [[1,3], [2,2], [3,1]]

Algorithm Comparison

Key Algorithmic Insights

1. Reverse Thinking

• Naive approach: Check each cell → both oceans (expensive)
• Optimal approach: Start from oceans → find reachable cells

2. Height Condition Logic

// Water flows TO higher/equal cells when starting FROM ocean
heights[newRow][newCol] >= heights[row][col]

3. Border Cell Handling

// Pacific: Top row + Left column
// Atlantic: Bottom row + Right column
// Careful with corner cells to avoid duplicates

4. Intersection Strategy

• Use separate boolean matrices for each ocean
• Final pass to find cells reachable from both

Both solutions efficiently solve the problem in O(m × n) time by leveraging the reverse flow insight and systematic exploration from ocean boundaries.