LeetCode Solution 417 - Pacific Atlantic Water Flow

Problem Statement:

Given an m x n matrix of non-negative integers representing the height of each cell, water can only flow up, down, left, or right and only to cells of equal or lesser height. Water can flow to the Pacific Ocean if it reaches the top or left edge and to the Atlantic Ocean if it reaches the bottom or right edge.

Return a list of grid coordinates where water can flow to both the Pacific and Atlantic oceans.

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

Output:

[[0,4],[1,3],[1,4],[2,2],[3,0],[3,1],[4,0]]

---

Optimal Approach: DFS (Depth First Search)

Approach Explanation:

• Use DFS to simulate the flow of water from the edges (Pacific and Atlantic).
• Maintain two matrices (pacific and atlantic) to track visited cells that can reach each ocean.
• Start DFS from the border cells and propagate inward.
• Collect coordinates that are reachable from both oceans.

C++ Solution:

class Solution {
public:
    vector<vector<int>> pacificAtlantic(vector<vector<int>>& heights) {
        if (heights.empty()) return {};
        int m = heights.size(), n = heights[0].size();
        vector<vector<bool>> pacific(m, vector<bool>(n, false));
        vector<vector<bool>> atlantic(m, vector<bool>(n, false));
        vector<vector<int>> result;
        
        // Lambda function for DFS
        auto dfs = [&](int r, int c, vector<vector<bool>>& ocean, auto&& dfs_ref) -> void {
            ocean[r][c] = true;
            vector<int> dir = {-1, 0, 1, 0, -1};
            for (int i = 0; i < 4; ++i) {
                int nr = r + dir[i], nc = c + dir[i + 1];
                if (nr >= 0 && nr < m && nc >= 0 && nc < n && !ocean[nr][nc] && heights[nr][nc] >= heights[r][c]) {
                    dfs_ref(nr, nc, ocean, dfs_ref);
                }
            }
        };
        
        // Perform DFS from Pacific and Atlantic borders
        for (int i = 0; i < m; ++i) {
            dfs(i, 0, pacific, dfs);
            dfs(i, n - 1, atlantic, dfs);
        }
        for (int j = 0; j < n; ++j) {
            dfs(0, j, pacific, dfs);
            dfs(m - 1, j, atlantic, dfs);
        }
        
        // Collect cells that can reach both oceans
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (pacific[i][j] && atlantic[i][j]) {
                    result.push_back({i, j});
                }
            }
        }
        return result;
    }
};

---

Step-by-Step Execution:

1. Initialization: Create pacific and atlantic matrices to track reachable cells.
2. DFS Traversal:
   • Start DFS from Pacific edge (left and top).
   • Start DFS from Atlantic edge (right and bottom).
   • Mark cells that can reach the respective ocean.
3. Finding Common Cells: Iterate through the matrix to find cells that are marked in both pacific and atlantic.
4. Output the Result: Return coordinates where water reaches both oceans.

---

Alternative Approaches & Why Not?

Approach	Time Complexity	Space Complexity	Drawback
Brute Force (Check every cell via DFS)	O(m * n * (m + n))	O(m * n)	Very slow for large grids
BFS instead of DFS	O(m * n)	O(m * n)	Similar complexity, but iterative
Dynamic Programming (DP)	O(m * n)	O(m * n)	Unintuitive and complex

Why DFS is the Best?

• DFS is efficient with O(m * n) complexity.
• Uses simple recursion.
• Intuitive approach with clear water flow simulation.

---

Complexity Analysis:

• Time Complexity: O(m * n) because each cell is visited at most twice (once for each ocean).
• Space Complexity: O(m * n) due to the visited matrices.

---

Conclusion:

• Best Approach: DFS with ocean border traversal.
• Key Idea: Start DFS from edges and mark reachable cells.
• Efficiency: O(m * n) time complexity.
• Alternative Practice Problems:
  • Number of Islands
  • Flood Fill
  • Surrounded Regions

This solution efficiently finds all valid points using DFS, making it optimal for large matrices.