#517

Hard

auto_awesomeGreedy choice plus invariant validation

LeetCode Problem Workspace

Super Washing Machines

Calculate the minimum moves to balance dresses across washing machines using a greedy strategy and invariant validation approach.

array greedy

Problem Statement

You are given n washing machines arranged in a line. Each machine initially contains some number of dresses or is empty. On each move, you may select any number of machines and pass one dress from each selected machine to an adjacent machine simultaneously.

Given an integer array machines where machines[i] represents the number of dresses in the i-th machine, determine the minimum number of moves required so that every washing machine has the same number of dresses. If achieving equal distribution is impossible, return -1.

Examples

Example 1

Input: machines = [1,0,5]

Output: 3

1st move: 1 0 1 1 4 2nd move: 1 2 1 3 3rd move: 2 1 2 2 2

Example 2

Input: machines = [0,3,0]

Output: 2

1st move: 0 1 2 0 2nd move: 1 2 --> 0 => 1 1 1

Example 3

Input: machines = [0,2,0]

Output: -1

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

Solution Approach

Check feasibility and compute target

Calculate the total number of dresses and divide by n to get the target dresses per machine. If the total cannot be evenly divided by n, return -1 immediately since equal distribution is impossible.

Use cumulative difference for greedy moves

Iterate through the machines while maintaining the running sum of differences between current machine dresses and the target. The maximum of absolute running sum or current difference gives the minimum moves at that point, reflecting simultaneous dress transfers.

Return maximum required moves

After scanning all machines, the overall minimum moves required is the maximum value obtained from the previous step. This ensures that all local imbalances and transfer constraints are accounted for in the final answer.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(n) because we iterate through the machines once to compute cumulative differences and track maximum moves. Space complexity is O(1) since we only store running totals and maximum values, making the approach efficient for large arrays.

What Interviewers Usually Probe

Checking if total dresses divisible by n reveals feasibility instantly.
Cumulative sum differences are key to applying greedy moves correctly.
Maximum of local imbalance or running sum identifies critical move bottleneck.

Common Pitfalls or Variants

Common pitfalls

Ignoring the need to check total dresses for divisibility leads to incorrect assumptions.
Confusing individual machine difference with cumulative difference causes underestimation of moves.
Assuming sequential transfers instead of simultaneous moves results in overcounting.

Follow-up variants

Allow transfers only in one direction along the array and recompute minimum moves.
Add constraints on maximum dresses a machine can hold and adjust greedy calculation.
Extend to 2D grid of machines and calculate moves based on row-wise and column-wise distributions.

FAQ

What is the main pattern used in Super Washing Machines problem?

The key pattern is greedy choice combined with invariant validation, where cumulative differences guide minimum moves.

Why do I need to check total dresses before proceeding?

Checking divisibility ensures that equal distribution is possible; otherwise, the problem has no solution and returns -1.

How do cumulative differences help in calculating moves?

They reflect the net imbalance at each step, allowing us to determine the maximum simultaneous moves needed across machines.

What is the time complexity of the optimal solution?

Time complexity is O(n) since we traverse the array once, tracking differences and maximum moves efficiently.

Can GhostInterview solve Super Washing Machines step by step?

Yes, it simulates each move, applying the greedy strategy, and explains why each step is necessary to reach balanced distribution.

terminal

Solution

Solution 1: 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$.

1

2

3

4

5

6

7

8

9

10

11

12

class Solution:
    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

Continue Practicing

#502 ipo #561 array partition #455 assign cookies