Java solution with explaination


  • 0
    C

    I have taken reference from other solution but felt there is a gap in explanation on how to calculate the minimum total move.

    For example lets consider 1D array 1,0,0,0,0,1,1

    Step 1:
    Lets compute number of steps required if we consider meeting point is at -1, in the above example it will be (1 + 6 + 7) = 14

    Step 2:
    count number of 1's which is 3

    Step 3:
    To find the most optimal meeting point we need to keep moving our assumed meeting point (which we assumed at index -1) one step right till we find a smaller or equal to previous result

    This is done in the code as

     sum = sum - numberOfRightCandidates + numberOfLeftCandidates;
    

    which means for each movement of assumed meeting point, all the 1's of right side of the meeting point needs to move one step less, and all the 1's on the left side of the meeting point needs to move one more step.

    in the code below a 2D array is converted to two 1D array by adding each rows and columns, above steps are performed for each arrays.

    Hope this explains how the minimum step is calculated. Cheers!

    public int minTotalDistance(int[][] grid) {
            if(grid.length == 0 || grid[0].length == 0){
                return 0;
            }
            
            int[] col = new int[grid[0].length], row = new int[grid.length];
            
            // finding sum of each columns and rows 
            for(int i=0; i<grid.length; i++){
                for(int j=0; j<grid[i].length; j++){
                    if(grid[i][j] == 1){
                        col[j] += 1;
                        row[i] += 1;
                    }
                }
            }
            
            return findMinimum(col) + findMinimum(row);
        }
        
        private int findMinimum(int[] arr){
            // sum of total moves taken if meeting point is at -1
            int sum = 0, numberOfRightCandidates = 0, numberOfLeftCandidates = 0;
            for(int i=0; i<arr.length; i++){
                sum += (i+1)*arr[i];
                numberOfRightCandidates += arr[i];
            }
            
            int min = sum;
            
            for(int i=0; i<arr.length; i++){
                // for each right move all right candidates needs to move one less step and left candidates needs to move one more step
                sum = sum - numberOfRightCandidates + numberOfLeftCandidates;
                if(sum <= min){
                    min = sum;
                }
                else{
                    break;
                }
                
                numberOfRightCandidates -= arr[i];
                numberOfLeftCandidates += arr[i];
            }
            
            return min;
        }
    

Log in to reply
 

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