LeetCode 517 - Super Washing Machines
The problem gives us a line of washing machines, where each machine contains some number of dresses. In one move, we are allowed to choose any subset of machines, and every chosen machine may pass exactly one dress to one of its adjacent machines simultaneously.
Difficulty: 🔴 Hard
Topics: Array, Greedy
Solution
Problem Understanding
The problem gives us a line of washing machines, where each machine contains some number of dresses. In one move, we are allowed to choose any subset of machines, and every chosen machine may pass exactly one dress to one of its adjacent machines simultaneously.
The goal is to make every washing machine contain the same number of dresses using the minimum number of moves. If it is impossible to distribute the dresses evenly, we must return -1.
The input array machines represents the number of dresses in each washing machine from left to right. For example:
machines = [1,0,5]
means:
- Machine 0 has 1 dress
- Machine 1 has 0 dresses
- Machine 2 has 5 dresses
The output is a single integer representing the minimum number of moves required to balance all machines.
The key detail is that during one move, multiple machines can transfer dresses simultaneously. This means we are not counting individual dress movements independently. Instead, we count synchronized rounds of transfers.
The constraints are important:
1 <= n <= 10^40 <= machines[i] <= 10^5
These limits tell us that:
- We cannot simulate every possible movement naively.
- We need an algorithm close to linear time.
- Since the total number of dresses may become large, careful reasoning is required.
A crucial observation is that balancing is only possible if the total number of dresses is divisible by the number of machines.
For example:
machines = [0,2,0]
total = 2
n = 3
Since 2 % 3 != 0, equal distribution is impossible.
Important edge cases include:
- A single machine, already balanced.
- All machines already equal.
- Cases where balancing is impossible because the total is not divisible by
n. - Large imbalances concentrated in one machine.
- Chains where dresses must travel through many intermediate machines.
Approaches
Brute Force Approach
A brute force strategy would explicitly simulate the redistribution process.
At every step, we could identify machines with excess dresses and transfer dresses toward neighboring machines with deficits. We would continue until all machines become balanced.
This approach is conceptually correct because it mimics the actual process described in the problem. However, it quickly becomes inefficient because:
- There may be many possible transfer choices at each step.
- Dresses may need to move long distances.
- Simulating every move individually can take enormous time.
In the worst case, the number of moves and state transitions can become extremely large. A direct simulation may approach quadratic or even exponential behavior depending on implementation.
Given n = 10^4, such an approach is not feasible.
Key Insight for the Optimal Approach
The optimal solution comes from understanding flow balance instead of simulating moves.
Suppose every machine should eventually contain:
target = total_dresses / n
For each machine:
difference = machines[i] - target
- Positive difference means the machine must send dresses out.
- Negative difference means the machine must receive dresses.
The deeper insight is that imbalance propagates across machine boundaries.
Define a running balance:
prefix_balance += machines[i] - target
This value represents how many dresses must flow across the boundary between machine i and machine i + 1.
Two quantities matter:
- The absolute value of the running balance.
This measures how many dresses must pass through a boundary. 2. The local surplus of a machine.
A machine with large surplus may need multiple moves because it can only send one dress per move.
The answer is therefore:
max(
abs(prefix_balance),
machines[i] - target
)
taken over all machines.
This leads to a linear-time greedy solution.
Approach Comparison
| Approach | Time Complexity | Space Complexity | Notes |
|---|---|---|---|
| Brute Force | Potentially O(n²) or worse | O(n) | Simulates transfers explicitly |
| Optimal | O(n) | O(1) | Uses balance flow observation |
Algorithm Walkthrough
- Compute the total number of dresses across all machines.
This determines whether balancing is possible at all. 2. Check divisibility.
If total % n != 0, return -1.
Equal distribution requires every machine to end with exactly the same number of dresses. 3. Compute the target number of dresses per machine.
target = total // n
- Initialize two variables:
running_balance = 0answer = 0
The running balance tracks net dress flow across boundaries. 5. Iterate through every machine.
For each machine:
difference = machines[i] - target
This tells us how many dresses this machine must give away or receive. 6. Update the running balance.
running_balance += difference
If the running balance is positive, extra dresses must move right.
If negative, dresses must move left. 7. Update the answer.
At every position:
answer = max(
answer,
abs(running_balance),
difference
)
We consider both:
- The flow through boundaries
- The local sending capacity of a machine
- Return the final answer.
Why it works
The running balance represents the exact number of dresses that must cross a boundary to achieve global balance. Since only one dress can cross from a machine per move, the required number of moves must be at least the maximum boundary flow.
Similarly, if a machine has surplus k, it needs at least k moves because it can only send one dress per move.
The algorithm computes the tightest lower bound imposed by all machines and all boundaries. That bound is achievable, so it is the optimal answer.
Python Solution
from typing import List
class Solution:
def findMinMoves(self, machines: List[int]) -> int:
total_dresses = sum(machines)
num_machines = len(machines)
if total_dresses % num_machines != 0:
return -1
target = total_dresses // num_machines
running_balance = 0
minimum_moves = 0
for dresses in machines:
difference = dresses - target
running_balance += difference
minimum_moves = max(
minimum_moves,
abs(running_balance),
difference
)
return minimum_moves
The implementation begins by computing the total number of dresses and verifying whether equal distribution is possible. If the total cannot be divided evenly among all machines, the function immediately returns -1.
Next, the algorithm computes the target number of dresses each machine should contain.
The variable running_balance tracks how many dresses must cross the current boundary as we scan from left to right. A positive balance means excess dresses must continue moving right. A negative balance means the left side still needs dresses from the right.
For each machine, we compute:
difference = dresses - target
This value measures the local surplus or deficit.
The final answer is updated using three quantities:
- The current answer
- The absolute running balance
- The local surplus
The maximum of these values determines the minimum number of moves required.
Because the algorithm only scans the array once, it runs efficiently in linear time.
Go Solution
func findMinMoves(machines []int) int {
totalDresses := 0
numMachines := len(machines)
for _, dresses := range machines {
totalDresses += dresses
}
if totalDresses%numMachines != 0 {
return -1
}
target := totalDresses / numMachines
runningBalance := 0
minimumMoves := 0
for _, dresses := range machines {
difference := dresses - target
runningBalance += difference
minimumMoves = max(
minimumMoves,
max(abs(runningBalance), difference),
)
}
return minimumMoves
}
func abs(x int) int {
if x < 0 {
return -x
}
return x
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
The Go implementation follows exactly the same logic as the Python solution.
One difference is that Go does not provide built in abs or max functions for integers, so helper functions are implemented manually.
Slices in Go behave similarly to dynamic arrays, so iterating through machines is straightforward using range.
Integer overflow is not a concern here because the constraints stay within Go's standard integer range.
Worked Examples
Example 1
machines = [1,0,5]
Total dresses:
1 + 0 + 5 = 6
Number of machines:
3
Target:
6 / 3 = 2
| Index | Dresses | Difference | Running Balance | Current Answer |
|---|---|---|---|---|
| 0 | 1 | -1 | -1 | 1 |
| 1 | 0 | -2 | -3 | 3 |
| 2 | 5 | 3 | 0 | 3 |
Final answer:
3
Example 2
machines = [0,3,0]
Target:
1
| Index | Dresses | Difference | Running Balance | Current Answer |
|---|---|---|---|---|
| 0 | 0 | -1 | -1 | 1 |
| 1 | 3 | 2 | 1 | 2 |
| 2 | 0 | -1 | 0 | 2 |
Final answer:
2
Example 3
machines = [0,2,0]
Total dresses:
2
Number of machines:
3
Since:
2 % 3 != 0
balancing is impossible.
Answer:
-1
Complexity Analysis
| Measure | Complexity | Explanation |
|---|---|---|
| Time | O(n) | Single pass through the array |
| Space | O(1) | Only a few variables are used |
The algorithm processes each machine exactly once, performing constant time work per iteration.
No auxiliary data structures proportional to input size are needed, so the extra space usage remains constant.
Test Cases
from typing import List
class Solution:
def findMinMoves(self, machines: List[int]) -> int:
total_dresses = sum(machines)
num_machines = len(machines)
if total_dresses % num_machines != 0:
return -1
target = total_dresses // num_machines
running_balance = 0
minimum_moves = 0
for dresses in machines:
difference = dresses - target
running_balance += difference
minimum_moves = max(
minimum_moves,
abs(running_balance),
difference
)
return minimum_moves
solution = Solution()
assert solution.findMinMoves([1, 0, 5]) == 3 # basic example
assert solution.findMinMoves([0, 3, 0]) == 2 # central surplus
assert solution.findMinMoves([0, 2, 0]) == -1 # impossible distribution
assert solution.findMinMoves([2, 2, 2]) == 0 # already balanced
assert solution.findMinMoves([10]) == 0 # single machine
assert solution.findMinMoves([4, 0, 0, 4]) == 2 # balanced from both ends
assert solution.findMinMoves([0, 0, 11, 5]) == 8 # large imbalance
assert solution.findMinMoves([1, 2, 3]) == 1 # small redistribution
assert solution.findMinMoves([9, 1, 8, 8, 9]) == 4 # mixed flow directions
assert solution.findMinMoves([100000, 0, 0, 0]) == 75000 # very large values
| Test | Why |
|---|---|
[1,0,5] |
Standard example with cascading transfers |
[0,3,0] |
Single machine distributes to both sides |
[0,2,0] |
Impossible distribution case |
[2,2,2] |
Already balanced input |
[10] |
Single machine boundary case |
[4,0,0,4] |
Transfers from both ends inward |
[0,0,11,5] |
Large imbalance concentrated near end |
[1,2,3] |
Small valid redistribution |
[9,1,8,8,9] |
Mixed surpluses and deficits |
[100000,0,0,0] |
Stress test with large numbers |
Edge Cases
One important edge case is when balancing is impossible because the total number of dresses is not divisible by the number of machines. A naive implementation might still attempt redistribution and produce an incorrect answer. The implementation avoids this by checking divisibility immediately and returning -1 before any further processing.
Another important case is when all machines are already balanced. For example:
[5,5,5,5]
In this situation, every machine already contains the target number of dresses. The running balance always remains zero, and the algorithm correctly returns 0.
A third subtle edge case occurs when one machine contains a very large surplus. For example:
[100000,0,0,0]
Even though dresses can move simultaneously, a single machine can only send one dress per move. The algorithm correctly accounts for this using the local surplus term:
difference = machines[i] - target
Without this check, an implementation might underestimate the required number of moves.
Another tricky scenario involves large cumulative imbalance across boundaries. Even if no single machine has a massive surplus, many dresses may still need to cross the same boundary. The running balance captures this exact requirement, ensuring the algorithm correctly handles long distance redistribution chains.