Super Washing Machines

Hard

#0502Time: O(N), where N is the number of washing machines. We iterate through the array three times: once to calculate the sum, once to build the prefix sum array, and once to find the maximum moves. This simplifies to O(N).Space: O(N), where N is the number of machines. This is required to store the prefix sum array.

Patterns

Greedy

Data structures

Array

Prompt

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 <= 10⁴
0 <= machines[i] <= 10⁵

Approaches

2 approaches with complexity analysis and trade-offs.

This approach first determines if a solution is possible by checking if the total number of dresses is divisible by the number of machines. If so, it calculates the target number of dresses for each machine. Then, it uses a prefix sum array to efficiently calculate the net flow of dresses across each boundary between machines. The minimum number of moves is determined by two potential bottlenecks: the maximum surplus of dresses in any single machine, and the maximum flow required across any boundary. The result is the maximum of these two values.

Algorithm

1. Calculate the total sum of dresses, total_dresses, from the machines array.
1. If total_dresses is not divisible by n (the number of machines), it's impossible to equalize the dresses. Return -1.
1. Calculate the target number of dresses per machine: avg = total_dresses / n.
1. Create a prefix sum array prefix_sum of size n. prefix_sum[i] will store the sum of dresses from machines[0] to machines[i].
1. Initialize max_moves = 0.
1. Iterate through the machines from i = 0 to n-1:
- a. Calculate the surplus for the current machine: surplus = machines[i] - avg. A machine with a surplus needs to give away dresses. The number of moves is limited by the machine that needs to give away the most. Update max_moves = Math.max(max_moves, surplus).
- b. Calculate the net flow of dresses across the boundary after machine i. This is the difference between the actual number of dresses in the prefix [0...i] and the target number of dresses for this prefix. The flow is flow = prefix_sum[i] - (i + 1) * avg.
- c. The number of moves must be at least abs(flow) to move that many dresses across the boundary. Update max_moves = Math.max(max_moves, Math.abs(flow)).
1. After the loop, max_moves will hold the minimum number of moves required. Return max_moves.

Walkthrough

The core idea is that the number of moves is constrained by the busiest point in the system. There are two types of bottlenecks:

A Single Machine's Workload: A machine i with machines[i] dresses needs to reach the avg. If machines[i] > avg, it has a surplus of machines[i] - avg dresses to pass to its neighbors. Since a machine can pass at most one dress per move, it needs at least machines[i] - avg moves. The minimum number of moves for the whole system must be at least the maximum surplus of any single machine.
Flow Between Sections: Consider the line of machines split into two parts at any point i: the left part [0...i-1] and the right part [i...n-1]. The total number of dresses in the left part is sum(machines[0...i-1]). The target for this part is i * avg. The difference, sum(machines[0...i-1]) - i * avg, represents the net number of dresses that must cross the boundary between machine i-1 and i. Since only one dress can cross this boundary per move, the number of moves must be at least the absolute value of this difference. We need to find the maximum flow required across any boundary.

This approach calculates these values by first building a prefix sum array to easily find the sum of any prefix [0...i]. Then, it iterates through the machines, updating the overall maximum moves required by considering both the individual machine surplus and the cumulative flow at each point.

1class Solution {2    public int findMinMoves(int[] machines) {3        int n = machines.length;4        int totalDresses = 0;5        for (int dresses : machines) {6            totalDresses += dresses;7        }8 9        if (totalDresses % n != 0) {10            return -1;11        }12 13        int avg = totalDresses / n;14        int[] prefixSum = new int[n];15        prefixSum[0] = machines[0];16        for (int i = 1; i < n; i++) {17            prefixSum[i] = prefixSum[i - 1] + machines[i];18        }19 20        int maxMoves = 0;21        for (int i = 0; i < n; i++) {22            // Bottleneck 1: A machine with a large surplus.23            int surplus = machines[i] - avg;24            maxMoves = Math.max(maxMoves, surplus);25 26            // Bottleneck 2: The flow of dresses between machine i and i+1.27            int flow = prefixSum[i] - (i + 1) * avg;28            maxMoves = Math.max(maxMoves, Math.abs(flow));29        }30 31        return maxMoves;32    }33}

Complexity

Time

O(N), where N is the number of washing machines. We iterate through the array three times: once to calculate the sum, once to build the prefix sum array, and once to find the maximum moves. This simplifies to O(N).

Space

O(N), where N is the number of machines. This is required to store the prefix sum array.

Trade-offs

Pros

Conceptually straightforward by separating prefix sum calculation from the main logic.
Correctly identifies the two main constraints on the number of moves.

Cons

Requires extra space proportional to the input size, which is suboptimal.

This is an optimized version of the prefix sum approach that achieves the same result with constant extra space. Instead of pre-calculating and storing all prefix sums in an array, we can calculate the required values on the fly in a single pass. We maintain a running sum (called balance) to track the net flow of dresses. This eliminates the need for an extra array, reducing the space complexity to O(1) while keeping the time complexity at O(N).

Algorithm

1. Calculate the total sum of dresses, total_dresses.
1. If total_dresses is not divisible by n, return -1.
1. Calculate the target avg = total_dresses / n.
1. Initialize max_moves = 0 and balance = 0. The balance variable will track the net flow of dresses from left to right.
1. Iterate through each machine's dress count dresses in the machines array:
- a. Calculate the surplus/deficit for the current machine: surplus = dresses - avg.
- b. Update the running balance with this value: balance += surplus. This balance now represents the cumulative flow needed across the boundary to the right of the current machine.
- c. Update max_moves by taking the maximum of its current value, the current machine's surplus, and the absolute value of the current balance. The formula is max_moves = Math.max(max_moves, Math.max(surplus, Math.abs(balance))).
1. After the loop, return max_moves.

Walkthrough

This approach is built on the same core logic as the prefix sum method: the minimum number of moves is the maximum of the two potential bottlenecks (individual machine surplus and cumulative flow). However, it calculates these values more efficiently.

We iterate through the machines just once. A balance variable is used to keep track of the cumulative sum of machines[i] - avg. At each step i, this balance is exactly equal to sum(machines[0...i]) - (i+1)*avg, which represents the net flow across the boundary after machine i.

In each iteration, we do the following:

Calculate surplus = machines[i] - avg. This is the number of dresses the current machine needs to give away.
Update the balance by adding the surplus. This balance now represents the total dresses that need to move from the left part [0...i] to the right.
Update the overall max_moves. The number of moves must be large enough for the machine with the biggest surplus (max(surplus)) and for the boundary with the largest flow (max(abs(balance))). We can combine these checks in each step:
- max_moves = Math.max(max_moves, surplus): This accounts for the first bottleneck.
- max_moves = Math.max(max_moves, Math.abs(balance)): This accounts for the second bottleneck.

By the end of the single loop, max_moves will have captured the maximum value required by either constraint across all machines and boundaries.

1class Solution {2    public int findMinMoves(int[] machines) {3        int n = machines.length;4        int totalDresses = 0;5        for (int d : machines) {6            totalDresses += d;7        }8 9        if (totalDresses % n != 0) {10            return -1;11        }12 13        int avg = totalDresses / n;14        int maxMoves = 0;15        int balance = 0; // Represents the net flow of dresses from left to right16 17        for (int dresses : machines) {18            // `dresses - avg` is how many dresses this machine is over/under the average.19            int surplus = dresses - avg;20 21            // `balance` tracks the cumulative surplus/deficit from the left.22            // A non-zero balance means dresses must be moved across the current position.23            balance += surplus;24 25            // The result is the maximum of three values:26            // 1. The max surplus of any single machine (max dresses to move out).27            // 2. The max absolute balance (max dresses to move across a boundary).28            maxMoves = Math.max(maxMoves, Math.max(surplus, Math.abs(balance)));29        }30 31        return maxMoves;32    }33}

Complexity

Time

O(N), where N is the number of washing machines. We iterate through the array twice: once to get the total sum and once to calculate the result. This is linear time.

Space

O(1), as we only use a few variables to store the total sum, average, running balance, and the result, regardless of the input size.

Trade-offs

Pros

Highly efficient, with optimal O(1) space complexity.
Solves the problem in a single pass after an initial sum calculation, leading to O(N) time complexity.

Cons

The logic of updating max_moves and balance in a single loop might be slightly less intuitive at first glance compared to the prefix sum approach.

Solutions

Solution

1class Solution {2public3  int findMinMoves(int[] machines) {4    int n = machines.length;5    int s = 0;6    for (int x : machines) {7      s += x;8    }9    if (s % n != 0) {10      return -1;11    }12    int k = s / n;13    s = 0;14    int ans = 0;15    for (int x : machines) {16      x -= k;17      s += x;18      ans = Math.max(ans, Math.max(Math.abs(s), x));19    }20    return ans;21  }22}

1class Solution {2public:3  int findMinMoves(vector<int> &machines) {4    int n = machines.size();5    int s = accumulate(machines.begin(), machines.end(), 0);6    if (s % n) {7      return -1;8    }9    int k = s / n;10    s = 0;11    int ans = 0;12    for (int x : machines) {13      x -= k;14      s += x;15      ans = max({ans, abs(s), x});16    }17    return ans;18  }19};

1class Solution:2    def findMinMoves(self, machines: List[int]) -> int: n = len(machines) k, mod = divmod(sum(machines), n) if mod: return - 1 ans = s = 0 for x in machines: x -= k s += x ans = max(ans, abs(s), x) return ans

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem