# Super Washing Machines
**Difficulty:** HARD
[External](https://leetcode.com/problems/super-washing-machines)
Canonical: https://scaleengineer.com/dsa/problems/super-washing-machines
**Patterns:** [Greedy](https://scaleengineer.com/dsa/patterns/greedy)
**Data structures:** Array
---
## Problem
You have `n` super washing machines on a line. Initially, each washing machine has some dresses or is empty.

For each move, you could choose any `m` (`1 <= m <= n`) washing machines, and pass one dress of each washing machine to one of its adjacent washing machines at the same time.

Given an integer array `machines` representing the number of dresses in each washing machine from left to right on the line, return _the minimum number of moves to make all the washing machines have the same number of dresses_. If it is not possible to do it, return `-1`.

**Example 1:**

**Input:** machines = [1,0,5]
**Output:** 3
**Explanation:**
1st move:    1     0 <-- 5    =>    1     1     4
2nd move:    1 <-- 1 <-- 4    =>    2     1     3
3rd move:    2     1 <-- 3    =>    2     2     2

**Example 2:**

**Input:** machines = [0,3,0]
**Output:** 2
**Explanation:**
1st move:    0 <-- 3     0    =>    1     2     0
2nd move:    1     2 --> 0    =>    1     1     1

**Example 3:**

**Input:** machines = [0,2,0]
**Output:** -1
**Explanation:**
It's impossible to make all three washing machines have the same number of dresses.

**Constraints:**

* `n == machines.length`
* `1 <= n <= 104`
* `0 <= machines[i] <= 105`

# Approaches
## Prefix Sum Approach
This approach first determines if a solution is possible by checking if the total number of dresses is divisible by the number of machines. If so, it calculates the target number of dresses for each machine. Then, it uses a prefix sum array to efficiently calculate the net flow of dresses across each boundary between machines. The minimum number of moves is determined by two potential bottlenecks: the maximum surplus of dresses in any single machine, and the maximum flow required across any boundary. The result is the maximum of these two values.
**Time:** O(N), where N is the number of washing machines. We iterate through the array three times: once to calculate the sum, once to build the prefix sum array, and once to find the maximum moves. This simplifies to O(N). · **Space:** O(N), where N is the number of machines. This is required to store the prefix sum array.
**Pros:** Conceptually straightforward by separating prefix sum calculation from the main logic.; Correctly identifies the two main constraints on the number of moves.
**Cons:** Requires extra space proportional to the input size, which is suboptimal.
### Explanation
The core idea is that the number of moves is constrained by the busiest point in the system. There are two types of bottlenecks:

1.  **A Single Machine's Workload:** A machine `i` with `machines[i]` dresses needs to reach the `avg`. If `machines[i] > avg`, it has a surplus of `machines[i] - avg` dresses to pass to its neighbors. Since a machine can pass at most one dress per move, it needs at least `machines[i] - avg` moves. The minimum number of moves for the whole system must be at least the maximum surplus of any single machine.

2.  **Flow Between Sections:** Consider the line of machines split into two parts at any point `i`: the left part `[0...i-1]` and the right part `[i...n-1]`. The total number of dresses in the left part is `sum(machines[0...i-1])`. The target for this part is `i * avg`. The difference, `sum(machines[0...i-1]) - i * avg`, represents the net number of dresses that must cross the boundary between machine `i-1` and `i`. Since only one dress can cross this boundary per move, the number of moves must be at least the absolute value of this difference. We need to find the maximum flow required across any boundary.

This approach calculates these values by first building a prefix sum array to easily find the sum of any prefix `[0...i]`. Then, it iterates through the machines, updating the overall maximum moves required by considering both the individual machine surplus and the cumulative flow at each point.

```java
class Solution {
    public int findMinMoves(int[] machines) {
        int n = machines.length;
        int totalDresses = 0;
        for (int dresses : machines) {
            totalDresses += dresses;
        }

        if (totalDresses % n != 0) {
            return -1;
        }

        int avg = totalDresses / n;
        int[] prefixSum = new int[n];
        prefixSum[0] = machines[0];
        for (int i = 1; i < n; i++) {
            prefixSum[i] = prefixSum[i - 1] + machines[i];
        }

        int maxMoves = 0;
        for (int i = 0; i < n; i++) {
            // Bottleneck 1: A machine with a large surplus.
            int surplus = machines[i] - avg;
            maxMoves = Math.max(maxMoves, surplus);

            // Bottleneck 2: The flow of dresses between machine i and i+1.
            int flow = prefixSum[i] - (i + 1) * avg;
            maxMoves = Math.max(maxMoves, Math.abs(flow));
        }

        return maxMoves;
    }
}
```
### Algorithm
*   1.  Calculate the total sum of dresses, `total_dresses`, from the `machines` array.
*   2.  If `total_dresses` is not divisible by `n` (the number of machines), it's impossible to equalize the dresses. Return -1.
*   3.  Calculate the target number of dresses per machine: `avg = total_dresses / n`.
*   4.  Create a prefix sum array `prefix_sum` of size `n`. `prefix_sum[i]` will store the sum of dresses from `machines[0]` to `machines[i]`.
*   5.  Initialize `max_moves = 0`.
*   6.  Iterate through the machines from `i = 0` to `n-1`:
    *   a.  Calculate the surplus for the current machine: `surplus = machines[i] - avg`. A machine with a surplus needs to give away dresses. The number of moves is limited by the machine that needs to give away the most. Update `max_moves = Math.max(max_moves, surplus)`.
    *   b.  Calculate the net flow of dresses across the boundary after machine `i`. This is the difference between the actual number of dresses in the prefix `[0...i]` and the target number of dresses for this prefix. The flow is `flow = prefix_sum[i] - (i + 1) * avg`.
    *   c.  The number of moves must be at least `abs(flow)` to move that many dresses across the boundary. Update `max_moves = Math.max(max_moves, Math.abs(flow))`.
*   7.  After the loop, `max_moves` will hold the minimum number of moves required. Return `max_moves`.

## Single Pass (Constant Space) Approach
This is an optimized version of the prefix sum approach that achieves the same result with constant extra space. Instead of pre-calculating and storing all prefix sums in an array, we can calculate the required values on the fly in a single pass. We maintain a running sum (called `balance`) to track the net flow of dresses. This eliminates the need for an extra array, reducing the space complexity to O(1) while keeping the time complexity at O(N).
**Time:** O(N), where N is the number of washing machines. We iterate through the array twice: once to get the total sum and once to calculate the result. This is linear time. · **Space:** O(1), as we only use a few variables to store the total sum, average, running balance, and the result, regardless of the input size.
**Pros:** Highly efficient, with optimal O(1) space complexity.; Solves the problem in a single pass after an initial sum calculation, leading to O(N) time complexity.
**Cons:** The logic of updating `max_moves` and `balance` in a single loop might be slightly less intuitive at first glance compared to the prefix sum approach.
### Explanation
This approach is built on the same core logic as the prefix sum method: the minimum number of moves is the maximum of the two potential bottlenecks (individual machine surplus and cumulative flow). However, it calculates these values more efficiently.

We iterate through the machines just once. A `balance` variable is used to keep track of the cumulative sum of `machines[i] - avg`. At each step `i`, this `balance` is exactly equal to `sum(machines[0...i]) - (i+1)*avg`, which represents the net flow across the boundary after machine `i`.

In each iteration, we do the following:
1.  Calculate `surplus = machines[i] - avg`. This is the number of dresses the current machine needs to give away.
2.  Update the `balance` by adding the `surplus`. This `balance` now represents the total dresses that need to move from the left part `[0...i]` to the right.
3.  Update the overall `max_moves`. The number of moves must be large enough for the machine with the biggest surplus (`max(surplus)`) and for the boundary with the largest flow (`max(abs(balance))`). We can combine these checks in each step:
    *   `max_moves = Math.max(max_moves, surplus)`: This accounts for the first bottleneck.
    *   `max_moves = Math.max(max_moves, Math.abs(balance))`: This accounts for the second bottleneck.

By the end of the single loop, `max_moves` will have captured the maximum value required by either constraint across all machines and boundaries.

```java
class Solution {
    public int findMinMoves(int[] machines) {
        int n = machines.length;
        int totalDresses = 0;
        for (int d : machines) {
            totalDresses += d;
        }

        if (totalDresses % n != 0) {
            return -1;
        }

        int avg = totalDresses / n;
        int maxMoves = 0;
        int balance = 0; // Represents the net flow of dresses from left to right

        for (int dresses : machines) {
            // `dresses - avg` is how many dresses this machine is over/under the average.
            int surplus = dresses - avg;

            // `balance` tracks the cumulative surplus/deficit from the left.
            // A non-zero balance means dresses must be moved across the current position.
            balance += surplus;

            // The result is the maximum of three values:
            // 1. The max surplus of any single machine (max dresses to move out).
            // 2. The max absolute balance (max dresses to move across a boundary).
            maxMoves = Math.max(maxMoves, Math.max(surplus, Math.abs(balance)));
        }

        return maxMoves;
    }
}
```
### Algorithm
*   1.  Calculate the total sum of dresses, `total_dresses`.
*   2.  If `total_dresses` is not divisible by `n`, return -1.
*   3.  Calculate the target `avg = total_dresses / n`.
*   4.  Initialize `max_moves = 0` and `balance = 0`. The `balance` variable will track the net flow of dresses from left to right.
*   5.  Iterate through each machine's dress count `dresses` in the `machines` array:
    *   a.  Calculate the surplus/deficit for the current machine: `surplus = dresses - avg`.
    *   b.  Update the running `balance` with this value: `balance += surplus`. This `balance` now represents the cumulative flow needed across the boundary to the right of the current machine.
    *   c.  Update `max_moves` by taking the maximum of its current value, the current machine's `surplus`, and the absolute value of the current `balance`. The formula is `max_moves = Math.max(max_moves, Math.max(surplus, Math.abs(balance)))`.
*   6.  After the loop, return `max_moves`.

# Solutions
### Java

```java
class Solution {
public
  int findMinMoves(int[] machines) {
    int n = machines.length;
    int s = 0;
    for (int x : machines) {
      s += x;
    }
    if (s % n != 0) {
      return -1;
    }
    int k = s / n;
    s = 0;
    int ans = 0;
    for (int x : machines) {
      x -= k;
      s += x;
      ans = Math.max(ans, Math.max(Math.abs(s), x));
    }
    return ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int findMinMoves(vector<int> &machines) {
    int n = machines.size();
    int s = accumulate(machines.begin(), machines.end(), 0);
    if (s % n) {
      return -1;
    }
    int k = s / n;
    s = 0;
    int ans = 0;
    for (int x : machines) {
      x -= k;
      s += x;
      ans = max({ans, abs(s), x});
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def findMinMoves(self, machines: List[int]) -> int: n = len(machines) k, mod = divmod(sum(machines), n) if mod: return - 1 ans = s = 0 for x in machines: x -= k s += x ans = max(ans, abs(s), x) return ans

```