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.length1 <= n <= 1040 <= machines[i] <= 105Problem Overview: You’re given an array where each index represents a washing machine and the value represents how many dresses it holds. In one move, any machine can pass one dress to an adjacent machine. The goal is to compute the minimum number of moves required so every machine ends up with the same number of dresses.
Approach 1: Brute Force Simulation (O(n^2) time, O(1) space)
A straightforward idea is to repeatedly simulate dress transfers until all machines hold the same amount. First compute the target number of dresses per machine (total / n). Then repeatedly scan the array and move dresses between neighbors whenever one machine has excess and the other has a deficit. This eventually balances the system but requires many passes over the array, leading to quadratic time. The approach works conceptually but becomes too slow for large inputs.
Approach 2: Greedy Load Balancing with Prefix Flow (O(n) time, O(1) space)
The optimal solution relies on a greedy observation about how dresses must flow across machines. First check if sum(machines) is divisible by n; otherwise balancing is impossible. Let avg be the target dresses per machine. Iterate through the array and compute the running imbalance balance += machines[i] - avg. This balance represents how many dresses must pass through this boundary to fix previous machines.
Two quantities determine the required moves. If a machine has machines[i] - avg extra dresses, it must send at least that many out. Also, the absolute value of the running prefix imbalance indicates how many dresses must flow across that boundary overall. The answer is the maximum of these two values across the array. This greedy reasoning works because dress transfers propagate like flow in a pipeline: the largest local surplus or the largest cumulative imbalance dictates the minimum number of moves.
The implementation uses only simple arithmetic while scanning the array once. No auxiliary structures are required. Although the logic looks subtle at first, it’s a classic load-balancing trick commonly seen in greedy problems where local surplus and prefix flow determine the global minimum operations.
Recommended for interviews: Interviewers expect the greedy prefix-flow solution with O(n) time and O(1) space. Discussing the simulation idea first shows you understand the mechanics of the process. Deriving the prefix imbalance insight demonstrates strong problem-solving and pattern recognition in array balancing problems.
The greedy approach involves determining the imbalance of dresses between adjacent machines and making moves to balance it. We find the maximum number of dresses that need to be moved either into or out of any machine to balance the system.
If it's impossible to balance the dresses equally among all machines (i.e., the total number of dresses is not divisible by the number of machines), the solution is -1.
This implementation starts by calculating the total number of dresses. If it isn't divisible by the number of machines, we return -1. Next, we calculate the difference between each machine's load and the average load, keeping a running balance, and determine the maximum number of moves by considering both the load difference and the accumulative balance, which is necessary due to passing dresses through intermediate machines.
Time Complexity: O(n), where n is the number of machines.
Space Complexity: O(1), since we use a constant amount of extra space.
If the total number of clothes in the washing machines cannot be divided evenly by the number of washing machines, it is impossible to make the number of clothes in each washing machine equal, so we directly return -1.
Otherwise, suppose the total number of clothes in the washing machines is s, then the number of clothes in each washing machine will eventually become k = s / n.
We define a_i as the difference between the number of clothes in the i-th washing machine and k, that is, a_i = machines[i] - k. If a_i > 0, it means that the i-th washing machine has extra clothes and needs to pass them to the adjacent washing machine; if a_i < 0, it means that the i-th washing machine lacks clothes and needs to get them from the adjacent washing machine.
We define the sum of the differences in the number of clothes in the first i washing machines as s_i = sum_{j=0}^{i-1} a_j. If we regard the first i washing machines as one group and the remaining washing machines as another group. Then if s_i is a positive number, it means that the first group of washing machines has extra clothes and needs to pass them to the second group of washing machines; if s_i is a negative number, it means that the first group of washing machines lacks clothes and needs to get them from the second group of washing machines.
Then there are the following two situations:
max_{i=0}^{n-1} \lvert s_i \rvert;max_{i=0}^{n-1} a_i.We take the maximum of the two.
The time complexity is O(n), where n is the number of washing machines. The space complexity is O(1).
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Greedy Approach | Time Complexity: O(n), where n is the number of machines. |
| Greedy | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Simulation | O(n^2) | O(1) | Useful for understanding how dresses move between machines; not practical for large inputs |
| Greedy Prefix Flow | O(n) | O(1) | Optimal approach for interviews and production; computes required moves using surplus and prefix imbalance |
LeetCode 517. Super Washing Machines • Happy Coding • 3,174 views views
Watch 8 more video solutions →Practice Super Washing Machines with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor