4ms java DP solution


  • 1
    A
      public int minTotalDistance(int[][] grid) {
        if(grid.length == 0 || grid[0].length == 0) return 0;
        int height = grid.length, width = grid[0].length, result = Integer.MAX_VALUE;
        // init + calcualte required info
        // leftOnes stores the # of 1's left of this col(inclusive)
        int leftOnes = 0, rightOnes = 0, count = 0, distance = 0;
        // topOnes[row] stores # of 1's above this row
        int[] topOnes = new int[height];
        int[] downOnes = new int[height];
        for(int row = 0; row < height; row++){
          for(int col = 0; col < width; col++){
            if(grid[row][col] == 1){
              rightOnes++;
              distance += row + col;
    ;        }
          }
        }
        count = rightOnes;
        int rowOnes = 0;
        for(int row = 0; row < height; row++){
          for(int cell : grid[row]) if(cell == 1) rowOnes++;
          downOnes[row] = count;
          count -= rowOnes;
          if(row + 1 < height) topOnes[row+1] = topOnes[row] + rowOnes;
          rowOnes = 0; // reset
        }
        /* dp:
          while travering each column, we keep its count of ones in this col(colOnes)
          rightOnes = rightOnes - colOnes
          leftOnes = leftOnes + last colOnes
        */
        int[] lookup = new int[height];
        for(int col = 0; col < width; col++){
          int colOnes = 0;
          for(int row = 0; row < height; row++){
            if(grid[row][col] == 1) colOnes++;
          }
          
          for(int row = 0; row < height; row++){
            if(row == 0 && col == 0) lookup[0] = distance; // initialize
            else if(row == 0) lookup[0] = lookup[0] + leftOnes - rightOnes;
            else lookup[row] = lookup[row-1] + topOnes[row] - downOnes[row];
            result = Math.min(result, lookup[row]);
          }
          leftOnes += colOnes;
          rightOnes -= colOnes;
          System.out.println(Arrays.toString(lookup));
        }
        return result;
      }
    

    When we make the choice from current cell the next cell:

    • if we move to right cell, all left 1's need to make one extra move, while all right 1's one less
    • if we move to next row, all up 1's need to make one extra move, while all down 1's one less

    O(row, col) = O(row, col-1) + leftOnes - rightOnes (col -> next col)

    = O(row-1, col) + upOnes - downOnes

    we need the global minimum


Log in to reply
 

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