3m java solution


  • 0
    B
    public class Solution {
        public int minTotalDistance(int[][] grid) {
            int[] horizontal = new int[grid[0].length];
            int[] vertical = new int[grid.length];
            for(int i = 0; i < grid.length; i++){
                for(int j = 0 ; j < grid[0].length; j++){
                    int people = grid[i][j];
                    horizontal[j] += people;
                    vertical[i] += people;
                }
            }
            int row = findMiddle(vertical);
            int col = findMiddle(horizontal);
            return row+col;
        }
        public static int findMiddle(int[] arr){
            int len = arr.length;
            int[] leftDis = new int[len];
            int[] rightDis = new int[len];
            int sum1 = 0;
            int sum2 = 0;
            for(int i = 1; i < len; i++){
                leftDis[i] = sum1 + leftDis[i-1] + arr[i-1];
                sum1 += arr[i-1];
                rightDis[len-1-i] = sum2 + rightDis[len- i] + arr[len-i];
                sum2 += arr[len-i] ;
            }
            int difference = Integer.MAX_VALUE;
            int mid = -1;
            for(int i = 0 ; i < len; i++){
                int total = leftDis[i] + rightDis[i];
                if(total < difference){
                    difference = total;
                    mid = i;
                }
            }
            return leftDis[mid] + rightDis[mid];
            
        }
    }

Log in to reply
 

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