Very intuitive O(n) solution


  • 14
    M

    Instead of using some DP methodology to solve the problem, I have a very intuitive way to approach the solution.

    Think about the machine i, after we make all machines have the same dresses, how many dresses will be passed through machine i?
    Let's denote the current sum of dresses of machines [0...i-1] as leftSums[i], and the current sum of dresses of machines [i+1...n-1] as rightSums[i].
    Let's denote the expected sum of dresses of machines [0...i-1] as expLeft, which means after all dresses are equally distributed, the sum of address in machines [0...i-1] should be expLeft. The same logic applies to machines [i+1...n-1], denoted as expRight.

    Then the above question should be clearly answered. If expLeft is larger than leftSums[i], that means no matter how you move the dresses, there will be at least expLeft - leftSums[i] dresses being moved to left of machine i, which means pass through machine i. For the right machines of machine i, the logic remains the same. So we could conclude that the minimum dresses passed through machine i will be:

    left = expLeft > leftSums[i] ? expLeft - leftSums[i] : 0;
    right = expRight > rightSums[i] ? expRight - rightSums[i] : 0;
    total = left + right;
    

    With this answer in mind, we could know that the minimum moves is the maximum dresses that pass through for each single machine, because for each dress, it will require at least one move. Hence the following solution. The code could be more concise, but I will leave it here for purpose of explanation.

    If you have any doubts or suggestions for this solution, any comments are welcome.

    public class Solution {
        public int findMinMoves(int[] machines) {
            int n = machines.length;
            int sum = 0;
            for (int num : machines) {
                sum += num;
            }
            if (sum % n != 0) {
                return -1;
            }
            int avg = sum / n;
            int[] leftSums = new int[n];
            int[] rightSums = new int[n];
            for (int i = 1; i < n; i ++) {
                leftSums[i] = leftSums[i-1] + machines[i-1];
            }
            for (int i = n - 2; i >= 0; i --) {
                rightSums[i] = rightSums[i+1] + machines[i+1];
            }
            int move = 0;
            for (int i = 0; i < n; i ++) {
                int expLeft = i * avg;
                int expRight = (n - i - 1) * avg;
                int left = 0;
                int right = 0;
                if (expLeft > leftSums[i]) {
                    left = expLeft - leftSums[i];
                } 
                if (expRight > rightSums[i]) {
                    right = expRight - rightSums[i];
                }
                move = Math.max(move, left + right);
            }
            return move;
        }
    }
    

  • 0
    S

    @mgispk
    It's great to see someone has the idea with me. To be honest, I'm still not very clear about the DP solution, and this one looks more intuitive to me.
    I used one array to record the 'flow' of dress from each machine to each direction. + means moving left while - means moving right.
    The problem description states n can be as large as 1e5 and dress can be 1e5 too. In this case we may have sum up to 1e10 which is greater than 2^31 - 1. So I use Long to compute everything, but looks like the test case doesn't cover it.
    Here's my solution.

    public class Solution {
        public int findMinMoves(int[] machines) {
            if(machines == null || machines.length == 0) return 0;
            long sum = 0;
            int n = machines.length;
            for(int m : machines) sum += m;
            if(sum % n != 0) return -1;
            long ave = sum / n;
            sum = 0;
            long[] flow = new long[n - 1];
            // For n machines, there're n - 1 slots in between. So we compute the flow of dress.
            // Positive means dress move to left, while negative right.
            for(int i = 0; i < n - 1; i++) {
                sum += machines[i];
                flow[i] = ave * (i + 1) - sum;
            }
            long res = 0;
            for(int i = 0; i < n; i++) {
                long left = i == 0 ? 0 : flow[i - 1];
                long right = i == n - 1 ? 0 : flow[i];
                // Below three IF conditions may not be needed, but it's good to show the idea.
                if(left > 0) res = Math.max(res, left);
                if(right < 0) res = Math.max(res, -right);
                // If there's dress flow out of current machine to both left and right, we need to 
                // add them because only one dress can be moved at one time.
                if(left > 0 && right < 0) res = Math.max(res, left - right);
            }
            return (int)res;
        }
    }
    

  • 1
    M

    @seeker_13 Nice catch for the overflow problem.


  • 0
    R

    Nice, I was trying to solve it a similar way.


  • 0

    More intuitive to understand than the top voted one. Upvoted


  • 0
    S

    Nice solution very intuitive and easy to understand than the other ones.
    I have a question, so at any index i either left || right has to be zero or both
    left & right are zero, left and right cannot be greater than zero at the same time right ?


Log in to reply
 

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