---
tags: leetcode
---

# [417. Pacific Atlantic Water Flow](https://leetcode.com/problems/pacific-atlantic-water-flow/)
---
# My Solution
## Solution 1: DFS
### The Key Idea for Solving This Coding Question
### C++ Code

class Solution {
public:
    vector<vector<int>> pacificAtlantic(vector<vector<int>> &heights) {
        rows = heights.size();
        cols = heights[0].size();

        vector<vector<bool>> pacificReachable(rows, vector<bool>(cols, false));
        vector<vector<bool>> atlanticReachable(rows, vector<bool>(cols, false));

        for (int r = 0; r < rows; ++r) {
            dfs(heights, pacificReachable, r, 0);
            dfs(heights, atlanticReachable, r, cols - 1);
        }
        for (int c = 0; c < cols; ++c) {
            dfs(heights, pacificReachable, 0, c);
            dfs(heights, atlanticReachable, rows - 1, c);
        }

        vector<vector<int>> answer;
        for (int r = 0; r < rows; ++r) {
            for (int c = 0; c < cols; ++c) {
                if (pacificReachable[r][c] && atlanticReachable[r][c]) {
                    answer.push_back({r, c});
                }
            }
        }

        return answer;
    }

private:
    int rows;
    int cols;

    void dfs(vector<vector<int>> &heights, vector<vector<bool>> &reachable, int r, int c) {
        reachable[r][c] = true;
        vector<vector<int>> dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

        for (auto &dir : dirs) {
            int nextR = r + dir[0], nextC = c + dir[1];
            if (nextR < 0 || rows <= nextR || nextC < 0 || cols <= nextC ||
                reachable[nextR][nextC] || heights[nextR][nextC] < heights[r][c]) {
                continue;
            }
            dfs(heights, reachable, nextR, nextC);
        }
    }
};

### Time Complexity
$O(mn)$
* $m$ is the number of rows of `heights`.
* $n$ is the number of columns of `heights`.
### Space Complexity
$O(mn)$
* $m$ is the number of rows of `heights`.
* $n$ is the number of columns of `heights`.
## Solution 2: BFS
### The Key Idea for Solving This Coding Question
### C++ Code

struct cellData {
    int r;
    int c;
    cellData(int r, int c) : r(r), c(c) {} 
};

class Solution {
public:
    vector<vector<int>> pacificAtlantic(vector<vector<int>> &heights) {
        rows = heights.size();
        cols = heights[0].size();

        vector<vector<bool>> pacificReachable(rows, vector<bool>(cols, false));
        vector<vector<bool>> atlanticReachable(rows, vector<bool>(cols, false));
        queue<cellData> pacificQ, atlanticQ;

        for (int r = 0; r < rows; ++r) {
            pacificQ.push(cellData(r, 0));
            pacificReachable[r][0] = true;

            atlanticQ.push(cellData(r, cols - 1));
            atlanticReachable[r][cols - 1] = true;
        }
        for (int c = 0; c < cols; ++c) {
            pacificQ.push(cellData(0, c));
            pacificReachable[0][c] = true;

            atlanticQ.push(cellData(rows - 1, c));
            atlanticReachable[rows - 1][c] = true;
        }

        bfs(heights, pacificQ, pacificReachable);
        bfs(heights, atlanticQ, atlanticReachable);

        vector<vector<int>> answer;
        for (int r = 0; r < rows; ++r) {
            for (int c = 0; c < cols; ++c) {
                if (pacificReachable[r][c] && atlanticReachable[r][c]) {
                    answer.push_back({r, c});
                }
            }
        }

        return answer;
    }

private:
    int rows;
    int cols;

    void bfs(vector<vector<int>> &heights, queue<cellData> &q, vector<vector<bool>> &reachable) {
        vector<vector<int>> dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

        while (!q.empty()) {
            cellData curr = q.front();
            q.pop();

            for (auto &dir : dirs) {
                int nextR = curr.r + dir[0], nextC = curr.c + dir[1];
                if (nextR < 0 || rows <= nextR || nextC < 0 || cols <= nextC ||
                    reachable[nextR][nextC] || 
                    heights[curr.r][curr.c] > heights[nextR][nextC]) {
                    continue;
                }
                q.push(cellData(nextR, nextC));
                reachable[nextR][nextC] = true;
            }
        }
    }
};

### Time Complexity
$O(mn)$
* $m$ is the number of rows of `heights`.
* $n$ is the number of columns of `heights`.
### Space Complexity
$O(mn)$
* $m$ is the number of rows of `heights`.
* $n$ is the number of columns of `heights`.
# Miscellane
<!--
# Test Cases

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

[[1]]

[[2,1],[1,2]]

* Runtime Error

[[1,2,3,4,5,6,7,8],[28,29,30,31,32,33,34,9],[27,48,49,50,51,52,35,10],[26,47,60,61,62,53,36,11],[25,46,59,64,63,54,37,12],[24,45,58,57,56,55,38,13],[23,44,43,42,41,40,39,14],[22,21,20,19,18,17,16,15]]

-->