417: Pacific-Atlantic-Water-Flow
Medium

table of contents

Simply, have 2 m by n matrices (where m denotes heights.size(), and n denotes heights[0].size()); one for the pacific ocean and the other for the atlantic ocean.

Then, you can just run BFS from every square cell that borders an island edge:

Afterwards, just iterate through and check both matrices to verify the cells that rain water can flow to both the pacific and atlantic oceans from.

code

class Solution {
public:
    vector<vector<int>> pacificAtlantic(vector<vector<int>>& heights) {
        int m = heights.size(), n = heights[0].size();
        vector<vector<int>> pacific (m, vector<int>(n));
        vector<vector<int>> atlantic (m, vector<int>(n));

        for (int i = 0; i < m; ++i) dfs(i, 0, pacific, heights);
        for (int j = 0; j < n; ++j) dfs(0, j, pacific, heights);

        for (int i = 0; i < m; ++i) dfs(i, n-1, atlantic, heights);
        for (int j = 0; j < n; ++j) dfs(m-1, j, atlantic, heights);

        vector<vector<int>> ans;
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (pacific[i][j] && atlantic[i][j]) {
                    ans.push_back({i, j});
                }
            }
        }
        return ans;
    }
private:
    vector<vector<int>> direction = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
    void dfs (int r, int c, vector<vector<int>>& ocean, vector<vector<int>>& heights) {
        ocean[r][c] = 1;
        for (int i = 0; i < 4; ++i) {
            int newR = r + direction[i][0], newC = c + direction[i][1];
            if (newR >= 0 && newC >= 0 && newR < ocean.size() && newC < ocean[0].size() && !ocean[newR][newC] && heights[r][c] <= heights[newR][newC]) {
                dfs(newR, newC, ocean, heights);
            }
        }
    }
};

complexity

time taken