Skip to main content
Talentd

Super Washing Machines - Solution & Explanation

HardArrayGreedy19 min readAsked at: Amazon, Google
Practice this problem

Problem Statement

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

Approach Overview

Problem 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 1: Greedy Approach

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.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n), where n is the number of machines.
Space Complexity: O(1), since we use a constant amount of extra space.

Try this approach in the editor →

Approach 2: Greedy

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:

  1. The maximum number of times clothes need to be moved between the two groups is max_{i=0}^{n-1} \lvert s_i \rvert;
  2. A washing machine in the group has too many clothes and needs to move clothes to both sides, the maximum number of times clothes need to be moved is 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).

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Greedy Approach

Time Complexity: O(n), where n is the number of machines.
Space Complexity: O(1), since we use a constant amount of extra space.

Greedy—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force SimulationO(n^2)O(1)Useful for understanding how dresses move between machines; not practical for large inputs
Greedy Prefix FlowO(n)O(1)Optimal approach for interviews and production; computes required moves using surplus and prefix imbalance

Video Solution

LeetCode 517. Super Washing Machines • Happy Coding • 3,283 views views

Watch 8 more video solutions →

Frequently Asked Questions

Is Super Washing Machines easy or hard?
Super Washing Machines is classified as a Hard problem on LeetCode. The implementation is short, but the challenge lies in recognizing the greedy insight that the maximum of local surplus and prefix imbalance determines the minimum moves.
Super Washing Machines Python/Java solution
Implement the greedy prefix-flow logic: compute the average, iterate through machines, maintain a running balance, and track the maximum required moves. The same logic works across Python, Java, C++, C#, and JavaScript with constant extra space.
How to solve Super Washing Machines in O(n)?
First check if the total number of dresses is divisible by the number of machines. Let avg be the target per machine. Iterate through the array and maintain balance += machines[i] - avg. Track the maximum of abs(balance) and machines[i] - avg across all indices; that value is the minimum moves required.
What is the best approach for Super Washing Machines?
The best approach is a greedy load-balancing technique using prefix imbalance. Compute the average dresses per machine, track the running balance while iterating, and take the maximum of local surplus and absolute prefix imbalance. This runs in O(n) time with O(1) extra space.
Is Super Washing Machines asked at Google/Amazon/Meta?
Super Washing Machines is a known hard-level greedy and array balancing problem and has appeared in interviews or practice sets associated with companies like Google, Amazon, and other large tech firms. It tests reasoning about load distribution and prefix flow.
What data structure is used in Super Washing Machines?
The problem primarily uses a simple array traversal. No complex data structures are required. The key idea is tracking prefix imbalance and local surplus while iterating through the array.
What is the time complexity of Super Washing Machines?
The optimal greedy solution runs in O(n) time because the array is scanned once while maintaining a running balance. Space complexity is O(1) since only a few variables are used. A naive simulation approach can degrade to O(n^2).

Ready to solve this problem?

Practice Super Washing Machines with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays