JAVA 17ms Solution, Simple and Clear, similar to Number of Islands's idea


  • 6

    The idea is as following:

    First, we can separate Pacific and Atlantic ocean into two, they share the same idea. The only difference is the starting position.

    Second, we think this problem in the opposite way: all the valid positions must have at least one path to connect to the ocean, so we start from the ocean to find out all the paths.

    1, 1, 1, 1
    1, 0, 0, 0
    1, 0, 0, 0
    1, 0, 0, 0

    Then we create a new boolean[][] matrix like above, all the beaches is marked as True (1) in the beginning, which means they can connect to the ocean, then we explore from the beach to find out all the paths. The idea is the same for Pacific and Atlantic.

    The last step is to use && to find positions satisfy both Pacific and Atlantic.

    Here comes the solution:

    static int[] dx = {-1,0,0,1};
    static int[] dy = {0,1,-1,0};
    public List<int[]> pacificAtlantic(int[][] matrix) {
        List<int[]> res = new ArrayList<>();
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) return res;
        boolean[][] pacific = new boolean[matrix.length][matrix[0].length];
        boolean[][] atlantic = new boolean[matrix.length][matrix[0].length];
        for (int i = 0; i < matrix.length; i++){
            pacific[i][0] = true;
            atlantic[i][matrix[0].length-1] = true;
        }
        for (int j = 0; j < matrix[0].length; j++){
            pacific[0][j] = true;
            atlantic[matrix.length-1][j] = true;
        }
        for (int i = 0; i < matrix.length; i++){
            explore(pacific, matrix, i, 0);
            explore(atlantic, matrix, i, matrix[0].length-1);
        }
        for (int j = 0; j < matrix[0].length; j++){
            explore(pacific, matrix, 0, j);
            explore(atlantic, matrix, matrix.length-1, j);
        }
        for (int i = 0; i < matrix.length; i++){
            for (int j = 0; j < matrix[0].length; j++){
                if (pacific[i][j] && atlantic[i][j] == true)
                    res.add(new int[]{i,j});
            }
        }
        return res;
        
    }
    private void explore(boolean[][] grid, int[][] matrix, int i, int j){
        grid[i][j] = true;
        for (int d = 0; d < dx.length; d++){
            if (i+dy[d] < grid.length && i+dy[d] >= 0 && 
                j + dx[d] < grid[0].length && j + dx[d] >= 0 && 
                grid[i+dy[d]][j+dx[d]] == false && matrix[i+dy[d]][j+dx[d]] >= matrix[i][j])
                    explore(grid, matrix, i+dy[d], j+dx[d]);
        }
    }

  • 0

    Brilliant! SImilar to '329. Longest Increasing Path in a Matrix' too~


  • 0
    M

    @markieff

    Brilliant! Thank you for sharing your solution.

    Notice that the first two for loops are not needed since the first thing the explore method does is setting the position to true.


  • 1
    A

    Maybe this part is unnecessary

        for (int i = 0; i < matrix.length; i++){
            pacific[i][0] = true;
            atlantic[i][matrix[0].length-1] = true;
        }
        for (int j = 0; j < matrix[0].length; j++){
            pacific[0][j] = true;
            atlantic[matrix.length-1][j] = true;
        }
    

  • 0
    J

    @PentaKill said in JAVA 17ms Solution, Simple and Clear, similar to Number of Islands's idea:

    Brilliant! SImilar to '329. Longest Increasing Path in a Matrix' too~

    I think this is just DFS solution similar to the top answer.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.