Java O(N) solution 15ms


  • 0
    F

    The basic idea is: if we meet with a contiguous positive numbers, then if they can flow into both directions, then that will be the best; but when? That's why I compute left and right arrays. If one of left or right of this positive volume is >= 0, then the positive volume can only flow in one direction. If both left and right are negative, then the volume can flow into both directions. The latter case is the tricky part: in this case, how to determine which part flow into which direction? If there is a i which can divide the positive volume evenly into left and right, (read the code to see how to), then the moves needed is Math.max(-left, -right), if not then one machine[i] will be divided into left and right.

    public class Solution {
        public int findMinMoves(int[] ma) {
            if(ma.length < 2) return 0;
            int[] left = new int[ma.length];
            int[] right = new int[ma.length];
            
            int sum1 = 0;
            for(int i : ma) sum1 += i;
            if(sum1 % ma.length != 0) return -1;
            int ave = sum1/ma.length;
            
            for(int i = 0; i < ma.length; i++){
                ma[i] -= ave;
            }
            
            sum1 = 0;
            for(int i = 1; i < ma.length; i++){
                sum1 = left[i] = sum1 + ma[i-1];
            }
    
            sum1 = 0;
            for(int i = ma.length - 2; i >= 0; i--){
                sum1 = right[i] = sum1 + ma[i+1];
            }
    
            int res = 0;
            for(int i = 0; i < ma.length; i++){
                if(ma[i] > 0){
                    int j = i, k = i;
                    sum1 = 0;
                    while(i < ma.length && ma[i] >= 0){
                        sum1 += ma[i++];
                    }
                    if(left[j] >= 0){
                        res = Math.max(res, sum1 + left[j]);
                    }else if(right[i-1] >= 0){
                        res = Math.max(res, sum1 + right[i-1]);
                    }else{
                        sum1 = left[j] + ma[j];
                        while(sum1 < 0 && ++j < i){
                            sum1 += ma[j];
                        }
                        int r = sum1;  // portion of ma[j] will be allocated to the right
                        int l = ma[j] - r; // portion of ma[j] will be allocated to the left
                        int rr = - right[i-1] - sum1 + left[k];  // positive volume with index > j && < i - 1; right of right
                        int ll = sum1 - ma[j] - left[k];  // positive volume with index > k && < j; left of left
                        
                        // Tricky part, try to understand.
                        if(r <= ll || l <= rr) res = Math.max(res, -Math.min(left[k], right[i-1])); 
                        else res = Math.max(res, ma[j]);
                    }
                }
            }
            return res;
        }
    }
    

Log in to reply
 

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