LeetCode 517: Super Washing Machines

Problem Restatement

We are given n washing machines in a line.

machines[i] is the number of dresses in the ith machine.

In one move, we may choose any number of machines. Each chosen machine passes exactly one dress to one adjacent machine at the same time.

We need to return the minimum number of moves needed to make every machine contain the same number of dresses.

If this is impossible, return -1.

The official problem states that any selected machines can simultaneously pass one dress to an adjacent machine, and asks for the minimum number of moves to make all machines equal.

Input and Output

Function shape:

class Solution:
    def findMinMoves(self, machines: List[int]) -> int:
        ...

Examples

Example 1:

machines = [1, 0, 5]

The total number of dresses is:

1 + 0 + 5 = 6

There are 3 machines, so each machine should end with:

6 / 3 = 2

One optimal process is:

[1, 0, 5] -> [1, 1, 4] -> [2, 1, 3] -> [2, 2, 2]

So the answer is:

3

Example 2:

machines = [0, 3, 0]

The total is 3, so each machine should have 1.

An optimal process takes 2 moves:

[0, 3, 0] -> [1, 2, 0] -> [1, 1, 1]

So the answer is:

2

Example 3:

machines = [0, 2, 0]

The total is 2.

There are 3 machines.

Since 2 cannot be evenly divided by 3, balancing is impossible.

So the answer is:

-1

First Thought: Simulate Moves

A direct idea is to simulate transfers.

At each step, find machines with too many dresses and move dresses toward machines with too few dresses.

This is hard to implement correctly because many moves happen simultaneously.

It is also inefficient because the number of moves can be large.

We need a formula that tells us the minimum number of parallel rounds directly.

Key Insight

First compute the target number of dresses per machine:

target = total // n

For each machine, define its balance:

balance = machines[i] - target

A positive balance means the machine must give away dresses.

A negative balance means it must receive dresses.

There are two lower bounds on the answer.

The first lower bound is local excess.

If a machine has x extra dresses, it can send out at most one dress per move. So the answer must be at least x.

The second lower bound is prefix flow.

For any boundary between machines, the total imbalance on the left side must cross that boundary. If the left prefix has p extra dresses, then p dresses must move to the right. If it has p missing dresses, then p dresses must move from the right.

So the answer must be at least:

abs(prefix_balance)

The final answer is the maximum of:

largest local excess
largest absolute prefix imbalance

Algorithm

1. Compute the total number of dresses.
2. If total % n != 0, return -1.
3. Compute target = total // n.
4. Scan machines from left to right.
5. Maintain prefix, the running imbalance.
6. For each machine:
   • compute diff = dresses - target
   • update prefix += diff
   • update the answer with abs(prefix)
   • update the answer with diff when diff is positive
7. Return the answer.

Correctness

If the total number of dresses is not divisible by the number of machines, no equal final distribution exists. Returning -1 is therefore correct.

Assume the total is divisible and the target is fixed.

For each machine, diff = machines[i] - target measures how many dresses that machine must send out if positive, or receive if negative. Since a machine can send at most one dress per move, any machine with positive diff requires at least diff moves.

For each prefix ending at index i, the running sum prefix measures the total surplus or deficit of machines 0 through i. To make this prefix balanced, abs(prefix) dresses must cross the boundary between i and i + 1. Since only one dress can cross that boundary per move, at least abs(prefix) moves are required.

So the answer must be at least the maximum of all positive local excesses and all absolute prefix imbalances.

This lower bound is also achievable: dresses can be routed along adjacent machines according to these prefix imbalances, and simultaneous moves allow independent transfers to happen in parallel. The maximum bottleneck, either one machine sending out many dresses or one boundary carrying many dresses, determines the number of required rounds.

Therefore the algorithm returns the minimum number of moves.

Complexity

Implementation

from typing import List

class Solution:
    def findMinMoves(self, machines: List[int]) -> int:
        total = sum(machines)
        n = len(machines)

        if total % n != 0:
            return -1

        target = total // n

        answer = 0
        prefix = 0

        for dresses in machines:
            diff = dresses - target
            prefix += diff

            answer = max(answer, abs(prefix), diff)

        return answer

Code Explanation

Compute the total number of dresses:

total = sum(machines)

If the total cannot be evenly split, return -1:

if total % n != 0:
    return -1

Compute the final number of dresses each machine should have:

target = total // n

prefix tracks how many dresses must flow across the current boundary:

prefix = 0

For each machine:

diff = dresses - target

diff is positive if the machine has extra dresses and negative if it needs dresses.

Update the running imbalance:

prefix += diff

Then update the answer:

answer = max(answer, abs(prefix), diff)

abs(prefix) handles boundary flow.

diff handles a single machine that must send out many dresses.

Finally:

return answer

Testing

def test_find_min_moves():
    s = Solution()

    assert s.findMinMoves([1, 0, 5]) == 3
    assert s.findMinMoves([0, 3, 0]) == 2
    assert s.findMinMoves([0, 2, 0]) == -1
    assert s.findMinMoves([2, 2, 2]) == 0
    assert s.findMinMoves([4, 0, 0, 4]) == 2
    assert s.findMinMoves([9, 1, 8, 8, 9]) == 4

    print("all tests passed")

Test meaning: