Code Implementation

class Solution:
    def findMinMoves(self, machines):
        total = sum(machines)
        n = len(machines)
        if total % n != 0:
            return -1
        target = total // n
        max_moves = 0
        curr = 0
        for load in machines:
            diff = load - target
            curr += diff
            max_moves = max(max_moves, abs(curr), diff)
        return max_moves
      

class Solution {
public:
    int findMinMoves(vector<int>& machines) {
        int total = 0, n = machines.size();
        for (int x : machines) total += x;
        if (total % n != 0) return -1;
        int target = total / n;
        int res = 0, curr = 0;
        for (int i = 0; i < n; ++i) {
            int diff = machines[i] - target;
            curr += diff;
            res = max(res, max(abs(curr), diff));
        }
        return res;
    }
};
      

class Solution {
    public int findMinMoves(int[] machines) {
        int total = 0, n = machines.length;
        for (int x : machines) total += x;
        if (total % n != 0) return -1;
        int target = total / n;
        int maxMoves = 0, curr = 0;
        for (int load : machines) {
            int diff = load - target;
            curr += diff;
            maxMoves = Math.max(maxMoves, Math.max(Math.abs(curr), diff));
        }
        return maxMoves;
    }
}
      

var findMinMoves = function(machines) {
    let total = machines.reduce((a, b) => a + b, 0);
    let n = machines.length;
    if (total % n !== 0) return -1;
    let target = Math.floor(total / n);
    let maxMoves = 0, curr = 0;
    for (let load of machines) {
        let diff = load - target;
        curr += diff;
        maxMoves = Math.max(maxMoves, Math.abs(curr), diff);
    }
    return maxMoves;
};
      

Problem Description

You are given an array machines where each element represents the number of dresses in a washing machine arranged in a row. In one move, you can choose any subset of machines and transfer one dress from each selected machine to one of its adjacent machines (left or right). The goal is to compute the minimum number of moves required to make every machine have the same number of dresses. If it is impossible, return -1.

• Each move can involve multiple machines, but each selected machine can only send one dress to an adjacent machine per move.
• All dresses must be distributed equally among all machines.
• There is always at most one valid way to distribute the dresses.
• Do not reuse dresses or machines arbitrarily; only adjacent transfers are allowed.

Thought Process

At first glance, one might think of simulating each possible move by shifting dresses left or right, but this quickly becomes inefficient for large arrays. Instead, we need to determine the minimum number of moves in a smarter way.

The key insight is to realize that the total number of dresses must be divisible by the number of machines for an equal distribution to be possible. If it's not, we immediately return -1.

Next, we observe that the number of moves required at each machine depends on two things:

• How many dresses it needs to give away or receive to reach the target
• The cumulative "imbalance" as we traverse the row of machines

Solution Approach

Let's break down the solution step by step:

1. Check Feasibility:
   • Sum all dresses in machines. If this sum is not divisible by the number of machines, return -1 as it's impossible to balance.
2. Calculate Target:
   • The target number of dresses per machine is total / n, where n is the number of machines.
3. Iterate and Track Imbalance:
   • Initialize a variable to track the running sum of surplus/deficit as you move through the array.
   • For each machine, calculate how many dresses it needs to give away (machines[i] - target).
   • Add this difference to the running sum.
   • The minimum number of moves needed at each step is the maximum of:
     • The absolute value of the running sum (since this represents the total flow of dresses that must pass through this point)
     • The current machine's surplus (since a machine can't send more than it has in a single move)
4. Result:
   • The answer is the maximum value found in the previous step as you scan the machines.

This approach ensures we account for both local and global imbalances, and efficiently computes the minimum moves required.

Example Walkthrough

Let's use the input [1, 0, 5]:

• Total dresses = 1 + 0 + 5 = 6. Number of machines = 3. Target per machine = 2.
• Machine 0: 1 - 2 = -1 (needs 1 dress)
• Machine 1: 0 - 2 = -2 (needs 2 dresses)
• Machine 2: 5 - 2 = 3 (has 3 extra dresses)

Now, scan through each machine, tracking the cumulative sum:

• After machine 0: cumulative = -1, max_moves = 1
• After machine 1: cumulative = -3, max_moves = 3
• After machine 2: cumulative = 0, max_moves = 3

The answer is 3. This matches the minimal number of moves needed to balance the machines:

• Step 1: Machine 2 gives 1 dress to machine 1 ([1,1,4])
• Step 2: Machine 2 gives 1 dress to machine 1 ([1,2,3])
• Step 3: Machine 2 gives 1 dress to machine 0 via machine 1 ([2,2,2])

Time and Space Complexity

Brute-force Approach:

• Simulating each move would be highly inefficient, potentially O(n^2) or worse, as dresses are shifted one by one.

• Time Complexity: O(n) — We iterate through the array once, performing constant-time operations per machine.
• Space Complexity: O(1) — Only a few variables are used for tracking sums and the result.

The optimized approach is highly efficient and scales well even for large input sizes.

Summary

The Super Washing Machines problem is elegantly solved by recognizing that the only way to balance the machines is by tracking the local and cumulative imbalances as we scan through the array. Instead of simulating each move, we compute the necessary transfers using a single pass, resulting in an efficient and clear solution. The main insights are checking divisibility for feasibility and using prefix sums to model flow, highlighting how mathematical reasoning leads to a simple, optimal algorithm.