15 lines Java


  • 0
    W

    dfs

    int[] dx = new int[] { -1, 1, 0, 0 }, dy = new int[] { 0, 0, 1, -1 };
    
    public List<int[]> pacificAtlantic(int[][] matrix) {
        List<int[]> result = new ArrayList<>();
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) return result;
        boolean[][] pacific = new boolean[matrix.length][matrix[0].length], atlantic = new boolean[matrix.length][matrix[0].length];
        for (int i = 0; i < matrix[0].length; dfs(matrix, pacific, 0, i++, Integer.MIN_VALUE));
        for (int i = 1; i < matrix.length; dfs(matrix, pacific, i++, 0, Integer.MIN_VALUE));
        for (int i = 0; i < matrix.length; dfs(matrix, atlantic, i++, matrix[0].length - 1, Integer.MIN_VALUE));
        for (int i = 0; i < matrix[0].length - 1; dfs(matrix, atlantic, matrix.length - 1, i++, Integer.MIN_VALUE));
        for (int i = 0; i < matrix.length; i++)
            for (int j = 0; j < matrix[0].length; j++)
                if (pacific[i][j] && atlantic[i][j]) result.add(new int[] { i, j });
        return result;
    }
    
    private void dfs(int[][] A, boolean[][] reach, int i, int j, int height) {
        if (i < 0 || i == A.length || j < 0 || j == A[0].length || reach[i][j] || A[i][j] < height) return;
        reach[i][j] = true;
        for (int k = 0; k < 4; dfs(A, reach, i + dx[k], j + dy[k++], A[i][j]));
    }

Log in to reply
 

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