LeetCode 517: Super Washing Machines

Problem Description

LeetCode Problem 517

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

Difficulty: Hard

Tags: array, greedy

Rating: 78.20%

Solution

Here’s my Python solution to this problem:

class Solution:
    def findMinMoves(self, machines: List[int]) -> int:
        s, n = sum(machines), len(machines)
        if s % n != 0: return -1

        target = s // n
        max_moves = 0
        running_diff = 0

        for d in machines:
            diff = d - target
            running_diff += diff

            # Take max of
            # abs(running_diff): total dresses that need to pass through this point
            # diff: dresses that need to move from/to this single machine
            max_moves = max(max_moves, abs(running_diff), diff)

        return max_moves

Example Walkthrough

Let’s walk through the example machines = [1, 0, 5]:

1. Calculate the total number of dresses and the number of machines.

   • s = 1 + 0 + 5 = 6
   • n = 3

2. Calculate the target number of dresses per machine.

   • target = s // n = 6 // 3 = 2

3. Initialize variables to keep track of the maximum moves and the running difference.

   • max_moves = 0
   • running_diff = 0

4. Iterate through each machine and calculate the difference between the current number of dresses and the target.

   • For the first machine (1), the difference is 1 - 2 = -1.
   • Update the running difference to -1.
   • Update the maximum moves to 1.

5. For the second machine (0), the difference is 0 - 2 = -2.

   • Update the running difference to -3.
   • Update the maximum moves to 3.

6. For the third machine (5), the difference is 5 - 2 = 3.

   • Update the running difference to 0.
   • Update the maximum moves to 3.

7. Return the maximum moves, which is 3.

Complexity Analysis

The solution has the following complexity characteristics:

• Time Complexity: $O(n)$
• Space Complexity: $O(1)$

Note: This is an automated analysis and may not capture all edge cases or specific algorithmic optimizations.