764. Largest Plus Sign.java

764. Largest Plus Sign(concise).java

    public int orderOfLargestPlusSign(int N, int[][] mines) {
        int[][] matrix = new int[N][N];
        for (int i = 0; i < N; i++) {
            Arrays.fill(matrix[i], 1);
        }
        for (int[] pair : mines) {
            matrix[pair[0]][pair[1]] = 0;
        }
        // calculate number of consecutive 1's in four directions: up, down, left, right
        int[][] left = new int[N][N];
        int[][] right = new int[N][N];
        int[][] up = new int[N][N];
        int[][] down = new int[N][N];
        int[][] dp = new int[N][N];
        int order = 0;
        // The left and up can be calculate together
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (matrix[i][j] == 1) {
                    left[i][j] = (j == 0) ? 1 : left[i][j - 1] + 1;
                    up[i][j] = (i == 0) ? 1 : up[i - 1][j] + 1;
                } 
            }
        }
        // The right and down can be calculate together
        for (int i = N - 1; i >= 0; i--) {
            for (int j = N - 1; j >= 0; j--) {
                if (matrix[i][j] == 1) {
                    right[i][j] = (j == N - 1) ? 1 : right[i][j + 1] + 1;
                    down[i][j] = (i == N - 1) ? 1: down[i + 1][j] + 1;
                    // dp[i][j] means max order in (i, j), dp[i][j] equals min number of consecutive 1's in four directions
                    dp[i][j] = Math.min(up[i][j], Math.min(down[i][j], Math.min(left[i][j], right[i][j])));  
                } 
                order = Math.max(order, dp[i][j]);
            }
        }
        return order;
    }

764. Largest Plus Sign(verbose).java

    public int orderOfLargestPlusSign(int N, int[][] mines) {
        int[][] matrix = new int[N][N];
        for (int i = 0; i < N; i++) {
            Arrays.fill(matrix[i], 1);
        }
        for (int[] pair : mines) {
            matrix[pair[0]][pair[1]] = 0;
        }
        int[][] left = countLeft(matrix);
        int[][] right = countRight(matrix);
        int[][] up = countUp(matrix);
        int[][] down = countDown(matrix);
        int[][] dp = new int[N][N];
        int order = 0;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (matrix[i][j] == 1) {
                    if (i == 0 || j == 0 || i == N - 1 || j == N - 1){
                        dp[i][j] = 1;
                    } else {
                        dp[i][j] = Math.min(up[i][j], Math.min(down[i][j], Math.min(left[i][j], right[i][j])));  
                    }
                    order = Math.max(order, dp[i][j]);
                } 
            }
        }
        return order;
    }
    private int[][] countLeft(int[][] matrix) {
        int N = matrix.length;
        int[][] left = new int[N][N];
        for (int i = 0; i < N; i++) {
            for (int j = N - 1; j >= 0; j--) {
                if (matrix[i][j] == 1) {
                    if (j == N - 1) {
                        left[i][j] = 1;
                    } else {
                        left[i][j] = left[i][j + 1] + 1;
                    }
                } 
            }
        }
        return left;
    } 
    private int[][] countRight(int[][] matrix) {
        int N = matrix.length;
        int[][] right = new int[N][N];
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (matrix[i][j] == 1) {
                    if (j == 0) {
                        right[i][j] = 1;
                    } else {
                        right[i][j] = right[i][j - 1] + 1;
                    }
                } 
            }
        }
        return right;
    }
    private int[][] countUp(int[][] matrix) {
        int N = matrix.length;
        int[][] up = new int[N][N];
        for (int j = 0; j < N; j++) {
            for (int i = N - 1; i >= 0; i--) {
                if (matrix[i][j] == 1) {
                    if (i == N - 1) {
                        up[i][j] = 1;
                    } else {
                        up[i][j] = up[i + 1][j] + 1;
                    }
                } 
            }
        }
        return up;
    } 
    private int[][] countDown(int[][] matrix) {
        int N = matrix.length;
        int[][] down = new int[N][N];
        for (int j = 0; j < N; j++) {
            for (int i = 0; i < N; i++) {
                if (matrix[i][j] == 1) {
                    if (i == 0) {
                        down[i][j] = 1;
                    } else {
                        down[i][j] = down[i - 1][j] + 1;
                    }
                } 
            }
        }
        return down;
    }