Pacific Atlantic Water Flow | JS, Python, Java, C++ | Easy DFS/Recursion/DP Solution w/ Explanation
(Note: This is part of a series of Leetcode solution explanations. If you like this solution or find it useful, please upvote this post.)\n\n---\n\n#### Idea:\n
*(Note: This is part of a series of Leetcode solution explanations. If you like this solution or find it useful,* ***please upvote*** *this post.)*\n\n---\n\n#### ***Idea:***\n\nIt should be obvious from the start that we\'ll need to solve this problem in reverse. We know that the edges of the input matrix (**M**) will flow water out to the ocean on their respective sides, and we can tell whether an adjacent cell will funnel water to the current cell, so we\'ll have to start from the edges and work our way inward.\n\nUnfortunately, since the path the water will take can possibly wind around, we can\'t do a straight one-time iteration. Instead, we\'ll have to use a **depth first search** (**DFS**) approach with either a **stack**/**queue** structure or **recursion**.\n\nFor each cell that touches an ocean, we\'ll have to follow the reverse path of the water up the continent as far as it will go. Since we only want cells that are reached by both oceans, we\'ll need a data structure to store the preliminary data for the cells while we wait for the opposite ocean to potentially find the same cell.\n\nThere are a few ways we can do this, but I\'ll choose a **dynamic programming** (**DP**) array (**dp**). Since there\'s no real reason to mimic the **2-D matrix** structure of **M**, we can just use a flattened **1-D array** instead, which should save some processing overhead. In order to store both oceans\' data discretely in **dp**, we can use **+1** for one and **+2** for the other. That means that when a cell goes to **3**, it should be added to our answer array (**ans**).\n\nOur DFS recursion function (**dfs**) should also check to make sure that we haven\'t already marked this cell with the current ocean (**w**) by using a **bitwise AND** (**&**) operator. Then, at the end of **dfs** we should fire off new recursions in all four directions, if possible.\n\n---\n\n#### ***Implementation:***\n\nJavascript can use the lighter, typed **Uint8Array** for **dp**.\n\n---\n\n#### ***Javascript Code:***\n\nThe best result for the code below is **100ms / 44.1MB** (beats 100% / 100%).\n```javascript\nvar pacificAtlantic = function(M) {\n    if (!M.length) return M\n    let y = M.length, x = M[0].length, ans = [],\n        dp = new Uint8Array(x * y)\n    const dfs = (i, j, w, h) => {\n        let ij = i * x + j\n        if ((dp[ij] & w) || M[i][j] < h) return\n        dp[ij] += w, h = M[i][j]\n        if (dp[ij] === 3) ans.push([i,j])\n        if (i + 1 < y) dfs(i+1, j, w, h)\n        if (i > 0) dfs(i-1, j, w, h)\n        if (j + 1 < x) dfs(i, j+1, w, h)\n        if (j > 0) dfs(i, j-1, w, h)\n    }   \n    for (let i = 0; i < y; i++) {\n        dfs(i, 0, 1, M[i][0])\n        dfs(i, x-1, 2, M[i][x-1])\n    }\n    for (let j = 0; j < x; j++) {\n        dfs(0, j, 1, M[0][j])\n        dfs(y-1, j, 2, M[y-1][j])\n    }\n    return ans\n};\n```\n\n---\n\n#### ***Python Code:***\n\nThe best result for the code below is **264ms / 15.6MB** (beats 97% / 53%).\n```python\nclass Solution:\n    def pacificAtlantic(self, M: List[List[int]]) -> List[List[int]]:\n        if not M: return M\n        x, y = len(M[0]), len(M)\n        ans, dp = [], [0] * (x * y)\n        def dfs(i: int, j: int, w: int, h: int):\n            ij = i * x + j\n            if dp[ij] & w or M[i][j] < h: return\n            dp[ij] += w\n            h = M[i][j]\n            if dp[ij] == 3: ans.append([i,j])\n            if i + 1 < y: dfs(i+1, j, w, h)\n            if i > 0: dfs(i-1, j, w, h)\n            if j + 1 < x: dfs(i, j+1, w, h)\n            if j > 0: dfs(i, j-1, w, h)\n        for i in range(y):\n            dfs(i, 0, 1, M[i][0])\n            dfs(i, x-1, 2, M[i][x-1])\n        for j in range(x):\n            dfs(0, j, 1, M[0][j])\n            dfs(y-1, j, 2, M[y-1][j])\n        return ans\n```\n\n---\n\n#### ***Java Code:***\n\nThe best result for the code below is **2ms / 40.4MB** (beats 100% / 43%).\n```java\nclass Solution {\n    static void dfs(int i, int j, int w, int h, int[][] M, byte[] dp, List<List<Integer>> ans) {\n        int ij = i * M[0].length + j;\n        if ((dp[ij] & w) > 0 || M[i][j] < h) return;\n        dp[ij] += w;\n        h = M[i][j];\n        if (dp[ij] == 3) ans.add(Arrays.asList(i,j));\n        if (i + 1 < M.length) dfs(i+1, j, w, h, M, dp, ans);\n        if (i > 0) dfs(i-1, j, w, h, M, dp, ans);\n        if (j + 1 < M[0].length) dfs(i, j+1, w, h, M, dp, ans);\n        if (j > 0) dfs(i, j-1, w, h, M, dp, ans);\n    }\n    public List<List<Integer>> pacificAtlantic(int[][] M) {\n        List<List<Integer>> ans = new ArrayList<>();\n        if (M.length == 0) return ans;\n        int y = M.length, x = M[0].length;\n        byte[] dp = new byte[x * y];\n        for (int i = 0; i < x; i++) {\n            dfs(0, i, 1, M[0][i], M, dp, ans);\n            dfs(y-1, i, 2, M[y-1][i], M, dp, ans);\n        }   \n        for (int i = 0; i < y; i++) {\n            dfs(i, 0, 1, M[i][0], M, dp, ans);\n            dfs(i, x-1, 2, M[i][x-1], M, dp, ans);\n        }\n        return ans;\n    }\n}\n```\n\n---\n\n#### ***C++ Code:***\n\nThe best result for the code below is **24ms / 16.7MB** (beats 100% / 99%).\n```c++\nclass Solution {\npublic:\n    vector<vector<int>> pacificAtlantic(vector<vector<int>>& M) {\n        vector<vector<int>> ans;\n        if (M.empty()) return ans;\n        int y = M.size(), x = M[0].size();\n        vector<char> dp(y * x);\n        for (int i = 0; i < y; i++) {\n            dfs(M, dp, i, 0, 1, 0);\n            dfs(M, dp, i, x - 1, 2, 0);\n        }\n        for (int i = 0; i < x; i++) {\n            dfs(M, dp, 0, i, 1, 0);\n            dfs(M, dp, y - 1, i, 2, 0);\n        }\n        for (int i = 0; i < y; i++) \n            for (int j = 0; j < x; j++) \n                if (dp[i * x + j] == 3) \n                    ans.push_back({i, j});\n        return ans;\n    }\nprivate:\n    void dfs(const vector<vector<int>>& M, vector<char>& dp, int i, int j, int w, int h) {\n        int y = M.size(), x = M[0].size(), ij = i * x + j, newh = M[i][j];;\n        if ((dp[ij] & w) || M[i][j] < h) return;\n        dp[ij] += w;\n        if (i + 1 < y) dfs(M, dp, i + 1, j, w, newh);\n        if (i > 0) dfs(M, dp, i - 1, j, w, newh);\n        if (j + 1 < x) dfs(M, dp, i, j + 1, w, newh);\n        if (j > 0) dfs(M, dp, i, j - 1, w, newh);\n    }\n};\n```
[]