82.1 (Approach 1) | ( O(m * n) )✅ | Python & C++(Step by step explanation)✅
Intuition\nThe problem asks to find the coordinates of cells from which water can flow to both the Pacific and the Atlantic oceans. Cells can flow water to adja
# Intuition\nThe problem asks to find the coordinates of cells from which water can flow to both the Pacific and the Atlantic oceans. Cells can flow water to adjacent cells if the adjacent cell has a higher or equal height. We need to find cells where water can flow to the Pacific Ocean and to the Atlantic Ocean.\n\n# Approach\n![image.png](https://assets.leetcode.com/users/images/0ef801c9-49b9-487e-824f-00b6316a35fa_1707855142.5285482.png)\n\n\n1. **Defining DFS Functions**:\n   - We\'ll start by defining a Depth-First Search (DFS) function to traverse the matrix and mark cells reachable from the Pacific and Atlantic oceans. This function will be called from the borders of the matrix.\n   \n2. **Traversing Borders**:\n   - We\'ll iterate through the top and bottom rows of the matrix, as well as the leftmost and rightmost columns. For each cell on these borders, we\'ll perform DFS to mark cells reachable from the Pacific Ocean if it\'s a top or left border cell, and from the Atlantic Ocean if it\'s a bottom or right border cell.\n\n3. **DFS Traversal**:\n   - During DFS traversal, starting from a border cell, we\'ll explore adjacent cells in all four directions (up, down, left, and right).\n   - We\'ll only move to adjacent cells with heights greater than or equal to the current cell\'s height to simulate water flowing.\n   - We\'ll continue DFS until we can\'t move further or until we\'ve visited a cell already marked as reachable.\n   - Each time we visit a cell, we\'ll mark it as reachable from the respective ocean.\n\n4. **Checking Accessibility**:\n   - After marking cells reachable from both oceans, we\'ll iterate through all cells in the matrix.\n   - For each cell, we\'ll check if it\'s marked as reachable from both the Pacific and Atlantic oceans. If so, we\'ll add its coordinates to the result list.\n\n5. **Returning Results**:\n   - Finally, we\'ll return the list of coordinates representing cells accessible from both oceans.\n\nThis approach effectively identifies cells that can flow water to both the Pacific and Atlantic oceans, allowing us to find areas that can reach both sides of the border.\n\n# Complexity\n- Time complexity: \\(O(m * n)\\), where \\(m\\) is the number of rows and \\(n\\) is the number of columns in the matrix. We perform DFS from the borders, and each cell is visited exactly once.\n- Space complexity: \\(O(m * n)\\) for the sets used to track reachable cells, and \\(O(k)\\) for the result list, where \\(k\\) is the number of cells accessible from both oceans.\n\n\n### Python Solution:\n\n```python\nclass Solution:\n    def pacificAtlantic(self, heights: List[List[int]]) -> List[List[int]]:\n        rows, cols = len(heights), len(heights[0])\n        pac, atl = set(), set()\n\n        # Define DFS function to traverse the matrix and mark cells reachable\n        def dfs(r, c, visit, prevHeight):\n            # Base cases for termination of DFS traversal\n            if (\n                (r, c) in visit\n                or r < 0\n                or c < 0\n                or r == rows\n                or c == cols\n                or heights[r][c] < prevHeight\n            ):\n                return\n            visit.add((r, c))\n            # Recursive calls for DFS traversal in four directions\n            dfs(r + 1, c, visit, heights[r][c])\n            dfs(r - 1, c, visit, heights[r][c])\n            dfs(r, c + 1, visit, heights[r][c])\n            dfs(r, c - 1, visit, heights[r][c])\n\n        # DFS from top and bottom borders to mark cells reachable by Pacific and Atlantic\n        for c in range(cols):\n            dfs(0, c, pac, heights[0][c])\n            dfs(rows - 1, c, atl, heights[rows - 1][c])\n\n        # DFS from left and right borders to mark cells reachable by Pacific and Atlantic\n        for r in range(rows):\n            dfs(r, 0, pac, heights[r][0])\n            dfs(r, cols - 1, atl, heights[r][cols - 1])\n\n        # Find cells reachable from both oceans and store their coordinates in res\n        res = []\n        for r in range(rows):\n            for c in range(cols):\n                if (r, c) in pac and (r, c) in atl:\n                    res.append([r, c])\n        return res\n```\n\n### C++ Solution:\n\n```cpp\nclass Solution {\npublic:\n    vector<vector<int>> pacificAtlantic(vector<vector<int>>& heights) {\n        int m = heights.size();\n        int n = heights[0].size();\n        \n        // Create matrices to mark visited cells for both oceans\n        vector<vector<bool>> pacific(m, vector<bool>(n));\n        vector<vector<bool>> atlantic(m, vector<bool>(n));\n        \n        // DFS traversal from top and bottom borders for both oceans\n        for (int i = 0; i < m; i++) {\n            dfs(heights, pacific, i, 0, m, n);\n            dfs(heights, atlantic, i, n - 1, m, n);\n        }\n        \n        // DFS traversal from left and right borders for both oceans\n        for (int j = 0; j < n; j++) {\n            dfs(heights, pacific, 0, j, m, n);\n            dfs(heights, atlantic, m - 1, j, m, n);\n        }\n        \n        // Find cells reachable from both oceans and store their coordinates in res\n        vector<vector<int>> res;\n        for (int i = 0; i < m; i++) {\n            for (int j = 0; j < n; j++) {\n                if (pacific[i][j] && atlantic[i][j]) {\n                    res.push_back({i, j});\n                }\n            }\n        }\n        \n        return res;\n    }\nprivate:\n    // DFS function to mark reachable cells from a given cell\n    void dfs(vector<vector<int>>& heights, vector<vector<bool>>& visited,\n        int i, int j, int m, int n) {\n        \n        visited[i][j] = true;\n        \n        // Recursive calls for DFS traversal in four directions\n        if (i > 0 && !visited[i - 1][j] && heights[i - 1][j] >= heights[i][j]) {\n            dfs(heights, visited, i - 1, j, m, n);\n        }\n        if (i < m - 1 && !visited[i + 1][j] && heights[i + 1][j] >= heights[i][j]) {\n            dfs(heights, visited, i + 1, j, m, n);\n        }\n        if (j > 0 && !visited[i][j - 1] && heights[i][j - 1] >= heights[i][j]) {\n            dfs(heights, visited, i, j - 1, m, n);\n        }\n        if (j < n - 1 && !visited[i][j + 1] && heights[i][j + 1] >= heights[i][j]) {\n            dfs(heights, visited, i, j + 1, m, n);\n        }\n    }\n};\n```\n\n\n\n# Please upvote the solution if you understood it.\n![1_3vhNKl1AW3wdbkTshO9ryQ.jpg](https://assets.leetcode.com/users/images/0161dd3b-ad9f-4cf6-8c43-49c2e670cc21_1699210823.334661.jpeg)\n
['Depth-First Search', 'Graph', 'Matrix', 'C++', 'Python3']