Sharing my DFS & BFS solution
Problems that are related to Graph, we usually utilize some classical graph traversal algorithms to work on.\nHere I\'m talking about Depth First Search dfs and
Problems that are related to `Graph`, we usually utilize some classical graph traversal algorithms to work on.\nHere I\'m talking about Depth First Search `dfs` and Breadth First Search `bfs`\n\nWe\'ll use 2 below options to solve this problem\n1. Recursive dfs, be careful if we have very deep graphs.\n1. Interative bfs, We use Queue\n\n**Idea**\nWe need 2 2D boolean arrays. One is to store capability of any cell `(ri, ci)` that from that cell whether water can flow to the pacific ocean, the other is to store capability of any cell `(ri, ci)` that from that cell whether water can flow to the atlantic ocean\n\nSo water can flow from cell `(ri, ci) ` to both the Pacific and Atlantic oceans, if and only if value of  cell `(ri, ci) ` in  2 boolean arrays both are `true`\n\n**BFS**\n```\nclass Solution {\n    int[][] dirs = new int[][]{{1,0},{0,1},{-1,0},{0,-1}};\n    public List<List<Integer>> pacificAtlantic(int[][] heights) {\n        int m = heights.length, n = heights[0].length;\n        \n        boolean[][] pacific = new boolean[m][n];\n        boolean[][] atlantic = new boolean[m][n];\n        \n        Queue<int[]> pQueue = new LinkedList<>();\n        Queue<int[]> aQueue = new LinkedList<>();\n        \n        for (int i = 0; i < m; i++) {\n            pQueue.offer(new int[]{i, 0});\n            pacific[i][0] = true;\n            aQueue.offer(new int[]{i, n-1});\n            atlantic[i][n-1] = true;\n        }\n        \n        for (int i = 0; i < n; i++) {\n            pQueue.offer(new int[]{0, i});\n            pacific[0][i] = true;\n            aQueue.offer(new int[]{m-1, i});\n            atlantic[m-1][i] = true;\n        }\n        bfs(heights, pQueue, pacific);\n        bfs(heights, aQueue, atlantic);\n        \n        List<List<Integer>> res = new ArrayList<>();\n        \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.add(Arrays.asList(i, j));\n                }\n            }\n        }\n        return res;\n    }\n    \n    private void bfs(int[][] heights, Queue<int[]> queue, boolean[][] visited) {\n        int m = heights.length, n = heights[0].length;\n        while (!queue.isEmpty()) {\n            int[] pos = queue.poll();\n            for (int[] dir : dirs) {\n                int x = pos[0] + dir[0];\n                int y = pos[1] + dir[1];\n                if (x < 0 || x >= m || y < 0 || y >= n || \n                    visited[x][y] || heights[x][y] < heights[pos[0]][pos[1]]) {\n                    continue;\n                }\n                visited[x][y] = true;\n                queue.offer(new int[]{x, y});\n            }\n        }\n    }\n}\n```\n\n**DFS**\n```\nclass Solution {\n    int[][] dirs = new int[][]{{1,0},{0,1},{-1,0},{0,-1}};\n    public List<List<Integer>> pacificAtlantic(int[][] heights) {\n        int m = heights.length, n = heights[0].length;\n        \n        boolean[][] pacific = new boolean[m][n];\n        boolean[][] atlantic = new boolean[m][n];\n        \n        for (int i = 0; i < m; i++) {\n            dfs(heights, pacific, Integer.MIN_VALUE, i, 0);\n            dfs(heights, atlantic, Integer.MIN_VALUE, i, n-1);\n        }\n        \n        for (int i = 0; i < n; i++) {\n            dfs(heights, pacific, Integer.MIN_VALUE, 0, i);\n            dfs(heights, atlantic, Integer.MIN_VALUE, m-1, i);\n        }\n        \n        List<List<Integer>> res = new ArrayList<>();\n        \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.add(Arrays.asList(i, j));\n                }\n            }\n        }\n        return res;\n    }\n    \n    private void dfs(int[][] heights, boolean[][] visited, int height, int x, int y) {\n        int m = heights.length, n = heights[0].length;\n        if (x < 0 || x >= m || y < 0 || y >= n || visited[x][y] || height > heights[x][y]) {\n            return;\n        }\n        visited[x][y] = true;\n        dfs(heights, visited, heights[x][y], x+1, y);\n        dfs(heights, visited, heights[x][y], x-1, y);\n        dfs(heights, visited, heights[x][y], x, y+1);\n        dfs(heights, visited, heights[x][y], x, y-1);\n    }\n}\n```\n\nTime Complexity: O(4mn)=O(mn) since a cell can be visited at most 4 times.
['Depth-First Search', 'Breadth-First Search', 'Java']