764. Largest Plus Sign

Link

Solution

1. Make a grid to traversal

2. for each grid[][], get the min extended length of four directions (up, down, left, right)

3. The max grid[][] will be the answer

  public int orderOfLargestPlusSign(int N, int[][] mines) {
        int[][] grids = new int[N][N];
        for(int i = 0; i < N; i++){
            Arrays.fill(grids[i], 1);
        }
        for(int[] mine : mines){
            grids[mine[0]][mine[1]] = 0;
        }
        int count = 0;
        for(int i = 0; i < N; i++){
            count = 0;
            for(int j = 0; j < N; j++){ //left continuos 1
                if(grids[i][j] == 0){
                    count = 0;
                }else{
                    count++;
                }
                grids[i][j] = count;
            }
            count = 0;
            for(int j = N-1; j >= 0; j--){//right continuos 1
                if(grids[i][j] == 0){
                    count = 0;
                }else{
                    count++;
                }
                grids[i][j] = Math.min(count, grids[i][j]);
            }
        }
        int ret = 0;                 
        for(int j = 0; j < N; j++){
            count = 0;
            for(int i = 0; i < N; i++){ //up continuous 1
                if(grids[i][j] == 0){
                    count = 0;
                }else{
                    count++;
                }
                grids[i][j] = Math.min(count, grids[i][j]);
            }
            count = 0;
            for(int i = N-1; i >= 0; i--){ //down
                if(grids[i][j] == 0){ 
                    count = 0;
                }else{
                    count++;
                }
                grids[i][j] = Math.min(count, grids[i][j]);
                ret = Math.max(grids[i][j], ret);
            }
        }
        return ret;
        
    }