Watch 9 video solutions for Super Washing Machines, a hard level problem involving Array, Greedy. This walkthrough by Happy Coding has 3,174 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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 |