Skip to content

← leetcode

Pacific Atlantic Water Flow

· Medium

LeetCode problem 417

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:

  • BFS for the pacific ocean from every square cell that borders the left and top edge
  • BFS for the atlantic ocean from every square cell that borders the right and bottom 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: O(mn) where m denotes heights.size() and n denotes heights[0].size()
  • Space: O(mn)

time taken

  • 27 minutes and 13 seconds