Super Washing Machines - Leetcode Solution

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 (m ≤ n) washing machines, and pass one dress of each washing machine to any one of the adjacent washing machines of your choice. Given an integer array representing the number of dresses in each washing machine from left to right on the line, you should find 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.

Solution: The idea for solving the problem is to find the total number of dresses in the given washing machines array. If the total number is not divisible by the number of washing machines then it is not possible to make all the machines have the same number of dresses. Else, we need to find the maximum dresses in a machine from the left side and the right side of the array. The minimum number of moves required will be the maximum difference between the left and right side's maximum dresses.

Algorithm:

1. Find the total number of dresses in the washing machines array.
2. Check if the total number is divisible by the number of washing machines. If not, return -1.
3. Initialize count, max_load, left_index, and right_index to 0.
4. Loop through the washing machines array: a. Subtract the current dress count from the total number of dresses. b. Calculate the new count by subtracting the total number of dresses from the current index multiplied by the number of dresses. c. Find the max load by finding the maximum value between the absolute value of the count and the dress count. d. Update the left index by finding the maximum value between the current index and the left index plus one if the count is negative. e. Update the right index by finding the maximum value between the current index and the right index minus one if the count is positive. f. Update the count by adding the current dress count to the total number of dresses.
5. Return the maximum load between the left and right side's maximum dresses.

Time Complexity: The time complexity of the above algorithm is O(n) since we are iterating through the entire washing machines array only once.

Space Complexity: The space complexity of the above algorithm is O(1) since we are only storing temporary variables.

Python Code:

class Solution: def findMinMoves(self, machines: List[int]) -> int: total_dresses = sum(machines) if total_dresses % len(machines) != 0: return -1 count, max_load, left_index, right_index = 0, 0, 0, len(machines) - 1 for i, dress in enumerate(machines): count += dress - (total_dresses // len(machines)) max_load = max(max_load, abs(count), dress - (total_dresses // len(machines))) if count < 0: left_index = max(left_index, i) if count > 0: right_index = min(right_index, i) return max(max_load, machines[right_index] - (total_dresses // len(machines)), machines[left_index] - (total_dresses // len(machines)))

1