417 Pacific Atlantic Water Flow

Techniques Used

• Graph
• DFS

Approach 1 (Brute-force, Slow)

• We maintain a flag variable (an array of length 2), storing the flag variables for both oceans. ie if flag[0] == 1 && flag[1] == 1 means that a particular cell can flow the water into both oceans, and thus can be added to our resultant list.
• Loop over the grid, initialize the flag and visited arrays for each cell, and if the above condition is met for a particular cell, we add it to the list.
• In the DFS utility function, we pass the grid, row, col values, along with the height of the current element (on which DFS is called), along with the visited array and the flag variable.
  • if the row < 0 || col < 0, this means that water has reached the pacific ocean.
    • so, we make the flag[0] == 1 and return.
  • or if the row >= heights.length || col >= heights[0].length , this means that water has reached the atlantic ocean
    • so, we make the flag[1] == 1 and return
  • if the current cell has been visited OR if the height of current cell is greater than the height provided, we return.
  • now, to process the current element
    • we mark the current cell as visited
    • we change the height variable to the height of the current cell (this height will be provided to the further recursion calls made on the neighbors of the current cell)
  • call this dfs function on the 4-directionally neighboring cells of the current cell.
• This approach is slow, because we are trying to maintain separate visited arrays for each cell, and losing the data from previous dfs calls made.
• This still passes all the test cases but is just slow.

Approach 2 (Optimized, Fast)

• Call the DFS function for all boundary elements of the grid, and fill the visited arrays for each of the oceans.
• Add all those row & col combinations (for which both the visited arrays have the true value) to the resultant list.
• In the DFS utility function,
  • We try to visit all the neighbors (4-directionally) which are taller than the current element.
  • If we have already visited this element or if its height is smaller than the height provided, or if it is out of bounds of grid, we return.

Complexity (Approach 1)

• Time Complexity: O(mn^2)
• Space Complexity: O(mn^2)

Complexity (Approach 2)

• Time Complexity: O(mn)
• Space Complexity: O(mn) for two visited arrays for each Ocean.

The code for both the approaches is provided below:

Note: Please let me if there is a mistake anywhere.

Code: Approach 2

class Solution {
    public List<List<Integer>> pacificAtlantic(int[][] heights) {


        int m = heights.length;
        int n = heights[0].length;

        List<List<Integer>> res = new ArrayList<>();

        boolean[][] pacificVisited = new boolean[m][n];
        boolean[][] atlanticVisited = new boolean[m][n];


        // call dfs on boundary elements, while searching for the bigger (higher) neighbors of each elements
        for(int row = 0; row < m; row++){
            dfs(heights, Integer.MIN_VALUE, row, 0, pacificVisited);
            dfs(heights, Integer.MIN_VALUE, row, n - 1, atlanticVisited);

        }

        for(int col = 0; col < n; col++){
            dfs(heights, Integer.MIN_VALUE, 0, col, pacificVisited);
            dfs(heights, Integer.MIN_VALUE, m - 1, col, atlanticVisited);

        }

        // all those cells which are present in both oceans' visited array, will be added to result
        for(int i = 0; i < m; i++){
            for(int j = 0; j < n; j++){
                if(pacificVisited[i][j] && atlanticVisited[i][j]){
                    List<Integer> cell = new ArrayList<>();
                    cell.add(i);
                    cell.add(j);
                    res.add(cell);
                }
            }
        }


        return res;

    }

    static void dfs(int[][] heights,  int height, int row, int col, boolean[][] visited){


        if(row < 0 || col < 0 || row >= heights.length || col >=  heights[0].length || visited[row][col] || heights[row][col] < height){

            return;

        } 

        visited[row][col] = true; 
        height = heights[row][col];

        dfs(heights, height, row - 1, col, visited);
        dfs(heights, height, row + 1, col, visited);
        dfs(heights, height, row, col - 1, visited);
        dfs(heights, height, row, col + 1, visited);


        return;


    }
}

Code: Approach 1

class Solution {
    public List<List<Integer>> pacificAtlantic(int[][] heights) {


        int m = heights.length;
        int n = heights[0].length;

        List<List<Integer>> res = new ArrayList<>();


        for(int i =  0; i < m; i++){
            for(int j =  0; j < n; j++){



                int[] flag = new int[2];
                boolean[][] visited = new boolean[m][n];
                int height = heights[i][j];
                dfs(heights, height, i, j, flag, visited);

                if(flag[0] == 1 && flag[1] == 1) {
                    // add to the list res
                    List<Integer> temp = new ArrayList<>();
                    temp.add(i);
                    temp.add(j);
                    res.add(temp);
                }
            }
        }


        return res;

    }

    // flag[0] = pacific
    // flag[1] = atlantic


    static void dfs(int[][] heights,  int height, int row, int col, int[] flag, boolean[][] visited){


        // able to flow into pacific
        if(row < 0 || col < 0){

            flag[0] = 1;
            return;

        } 

        //able to flow into atlantic
        if(row >= heights.length || col >=  heights[0].length){

            flag[1] = 1;
            return;
        }

        if(visited[row][col]) return;

        if(heights[row][col] > height){
            return;
        }
        visited[row][col] = true; //marked as visited
        height = heights[row][col];

        dfs(heights, height, row - 1, col, flag, visited);
        dfs(heights, height, row + 1, col, flag, visited);
        dfs(heights, height, row, col - 1, flag, visited);
        dfs(heights, height, row, col + 1, flag, visited);


        return;


    }
}