EASY DFS SOLUTION || 99.30% FASTER
\nclass Solution {\n    \n    int[][] dir = {{0,-1}, {-1,0}, {0,1}, {1,0}};\n    public List<List<Integer>> pacificAtlantic(int[][] heights) {\n        \n      
```\nclass Solution {\n    \n    int[][] dir = {{0,-1}, {-1,0}, {0,1}, {1,0}};\n    public List<List<Integer>> pacificAtlantic(int[][] heights) {\n        \n        int m = heights.length, n = heights[0].length, i, j;\n        \n        // mark true to all the cells that can flow to pacific ocean\n        boolean[][] pacific = new boolean[m][n];\n        for(i = 0; i < n; i++) bfs(heights, 0, i, pacific); // first row \n        for(i = 0; i < m; i++) bfs(heights, i, 0, pacific); // first column\n        \n        // mark true to all the cells that can flow to atlantic ocean\n        boolean[][] atlantic = new boolean[m][n];\n        for(i = n-1; i >= 0; i--) bfs(heights, m-1, i, atlantic); // last row\n        for(i = m-1; i >= 0; i--) bfs(heights, i, n-1, atlantic); // last column\n        \n        // find the cell of rain water that can flow to both ocean\n        List<List<Integer>> output = new ArrayList<>();\n        for(i = 0; i < m; i++){\n            for(j = 0; j < n; j++){\n                if(atlantic[i][j] && pacific[i][j])\n                    output.add(new ArrayList<>(List.of(i, j)));\n            }\n        }\n        return output;\n    }\n    \n    void bfs(int[][] heights, int r, int c, boolean[][] ans){\n        \n        ans[r][c] = true; // mark reachable\n        for(int i = 0; i < dir.length; i++){\n            \n            int newr = r+dir[i][0];\n            int newc = c+dir[i][1];\n            if(newr<0 || newc<0 || newr>=heights.length || newc>=heights[0].length || ans[newr][newc] || heights[newr][newc] < heights[r][c])\n                continue;\n            \n            bfs(heights, newr, newc, ans);\n        }\n    }\n}\n```
['Depth-First Search', 'Java']