{x}
blog image

Super Washing Machines

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

Solution Explanation: Super Washing Machines

This problem asks for the minimum number of moves to equalize the number of dresses in each washing machine. The solution leverages a greedy approach and clever use of prefix sums to achieve linear time complexity.

Intuition:

The core idea is that we don't need to simulate the movement of dresses one by one. Instead, we can analyze the net movement required. If the total number of dresses isn't divisible by the number of machines, the task is impossible. Otherwise, we can determine the target number of dresses per machine. The problem then reduces to finding the maximum imbalance at any point along the washing machine line.

Algorithm:

  1. Check Feasibility: Calculate the total number of dresses. If it's not divisible by the number of machines (n), return -1 because equal distribution is impossible.

  2. Calculate Target: Determine the target number of dresses per machine (k) by dividing the total number of dresses by n.

  3. Calculate Differences: For each machine, calculate the difference (a[i]) between its current number of dresses and the target (k). a[i] can be positive (excess dresses) or negative (deficient dresses).

  4. Prefix Sum: Compute the prefix sum (s[i]) of the differences. s[i] represents the cumulative difference up to machine i. The absolute value of s[i] indicates the net number of dresses that need to be moved across the point between machine i and i+1.

  5. Find Maximum Imbalance: The minimum number of moves is the maximum of two values:

    • max(|s[i]|): The maximum absolute prefix sum represents the maximum number of dresses that need to be transported across any point between machines.
    • max(a[i]): The maximum individual difference represents the maximum number of dresses a single machine needs to give away (or receive). This is because a machine might need to send dresses to both neighbors simultaneously.

Time and Space Complexity:

  • Time Complexity: O(n) - We iterate through the machines array once to calculate the total dresses, differences, and prefix sums.
  • Space Complexity: O(1) - We use only a few constant extra variables.

Code Examples (Python):

class Solution:
    def findMinMoves(self, machines: List[int]) -> int:
        total_dresses = sum(machines)
        n = len(machines)
        
        if total_dresses % n != 0:
            return -1
        
        target_dresses = total_dresses // n
        diffs = [m - target_dresses for m in machines]
        prefix_sum = 0
        max_abs_prefix_sum = 0
        max_diff = 0
        
        for diff in diffs:
            prefix_sum += diff
            max_abs_prefix_sum = max(max_abs_prefix_sum, abs(prefix_sum))
            max_diff = max(max_diff, diff)
        
        return max(max_abs_prefix_sum, max_diff)

The code in other languages (Java, C++, Go, TypeScript) follows the same logic, only differing in syntax. The key is the efficient use of prefix sums and the identification of the two crucial maximum values to determine the minimum moves.