Unique, Compact and Fast (3ms - 99% ) solution with explanation
Intuition\nDFS\n\n# Approach\nHere\'s a step-by-step explanation of the code:\n\n1. The pacificAtlantic method is the entry point of the solution. It takes the 
# Intuition\nDFS\n\n# Approach\nHere\'s a step-by-step explanation of the code:\n\n1. The pacificAtlantic method is the entry point of the solution. It takes the heights matrix as input and returns a list of lists of integers representing the coordinates of the cells where water can flow to both oceans.\n\n2. The visited matrix is a 2D array of integers with the same dimensions as the heights matrix, used to keep track of visited cells. It is initialized with all values set to 0.\n\n3. The ans list is used to store the final result - the list of lists of coordinates.\n\n4. The first two nested loops iterate over the first and last row of the heights matrix, and the dfs method is called for each cell in these rows. The dfs method is called with the row index, column index, heights matrix, visited matrix, mark (1 or 2) representing which ocean the water is flowing to, current height of the cell, and the ans list.\n\n5. The second pair of nested loops iterate over the first and last column of the heights matrix, and the dfs method is called for each cell in these columns, similar to step 4.\n\n6. The dfs method is a recursive function that performs the depth-first search. It takes the current row index, column index, heights matrix, visited matrix, mark, current height of the cell, and the ans list as input.\n\n7. The dfs method starts by checking if the current cell is out of bounds (i.e., row or column index is less than 0 or greater than or equal to the dimensions of the heights matrix), or if the height of the current cell is less than the height of the previous cell (i.e., water can\'t flow uphill), or if the current cell has already been visited by the same ocean (mark) or by both oceans (mark=3). If any of these conditions are true, the function returns early and does not further explore the current cell.\n\n8. If the current cell passes the above checks, it is marked as visited by adding the mark to the visited matrix at the current row and column index.\n\n9. If the current cell has been visited by both oceans (mark=3), its coordinates (row and column index) are added to the ans list as a new list of integers representing the coordinates.\n\n10. The dfs method is then recursively called for the neighboring cells (up, down, left, and right) of the current cell, passing the updated row and column indices, mark, and the height of the current cell.\n\n11. After the DFS traversal is complete, the ans list contains the coordinates of the cells where water can flow to both oceans.\n\n12. Finally, the ans list is returned as the solution to the problem.\n\n# Complexity\n- Time complexity:\nO(m*n)\n\n- Space complexity:\nO(m*n)\n\n# Code\n```\nclass Solution {\n    public List<List<Integer>> pacificAtlantic(int[][] heights) {\n        int visited[][] = new int[heights.length][heights[0].length];\n        List<List<Integer>>ans =  new ArrayList<>();\n        for(int i=0;i<heights[0].length;i++){\n            dfs(0,i,heights,visited,1,heights[0][i],ans);\n            dfs(heights.length-1,i,heights,visited,2,heights[heights.length-1][i],ans);\n        }\n        for(int i=0;i<heights.length;i++){\n            dfs(i,0,heights,visited,1,heights[i][0],ans);\n            dfs(i,heights[0].length-1,heights,visited,2,heights[i][heights[0].length-1],ans);\n        }\n        return ans;\n    }\n    private void dfs(int i , int j ,int[][] heights, int[][] visited, int mark, int ch, List<List<Integer>> ans){\n        if(i<0 || j<0 || i>=heights.length || j>=heights[0].length || heights[i][j]<ch || visited[i][j]==mark || visited[i][j]==3) return ;\n        visited[i][j]+=mark;\n        if(visited[i][j]==3){\n            ans.add(new ArrayList<>(Arrays.asList(i,j)));\n        }\n        dfs(i+1,j,heights,visited,mark,heights[i][j],ans);\n        dfs(i,j+1,heights,visited,mark,heights[i][j],ans);\n        dfs(i-1,j,heights,visited,mark,heights[i][j],ans);\n        dfs(i,j-1,heights,visited,mark,heights[i][j],ans);\n    }\n}\n```
['Array', 'Depth-First Search', 'Matrix', 'Java']