Last updated on January 17th, 2025 at 01:02 am
Here, we see a Super Washing Machines LeetCode Solution. This Leetcode problem is solved using different approaches in many programming languages, such as C++, Java, JavaScript, Python, etc.
List of all LeetCode Solution
Topics
Dynamic Programming, Math
Companies
Amazon
Level of Question
Hard
Super Washing Machines LeetCode Solution
Table of Contents
1. 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 (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.
2. Coding Pattern Used in Solution
The coding pattern used in this code is “Prefix Sum with Greedy Approach”. This pattern involves maintaining a running sum (prefix sum) to track the cumulative difference between the current state and the target state, and using a greedy approach to determine the maximum number of moves required to balance the machines.
3. Code Implementation in Different Languages
3.1 Super Washing Machines C++
class Solution {
public:
int findMinMoves(vector<int>& machines) {
int sum = 0, n = machines.size();
for(auto &i: machines)sum += i;
if(sum%n)return -1;
sum /= n;
int k = 0;
int ans = 0;
for(auto &i: machines){
k += i-sum;
ans = max({(i-sum),ans,abs(k)});
}
return ans;
}
};
3.2 Super Washing Machines Java
class Solution {
public int findMinMoves(int[] machines) {
int avg = 0;
for(int i = 0; i < machines.length; i++){
avg += machines[i];
}
if(avg % machines.length != 0){
return -1;
}
int res = 0, cnt = 0;
avg = avg / machines.length;
for (int m : machines) {
cnt += m - avg;
res = Math.max(res, Math.max(Math.abs(cnt), m - avg));
}
return res;
}
}
3.3 Super Washing Machines JavaScript
var findMinMoves = function(machines) {
let load, tot = 0, max = 0;
let sum = machines.reduce((a, x) => a + x);
let target = sum / machines.length;
if (target % 1) return -1;
machines.forEach(n => {
load = n - target;
tot += load;
max = Math.max(max, Math.abs(tot), load);
})
return max;
};
3.4 Super Washing Machines Python
class Solution(object):
def findMinMoves(self, machines):
n = len(machines)
Sum = sum(machines)
if Sum % n:
return -1
final = Sum//n
moves = prefix = 0
for i in machines:
diff = i - final
prefix += diff
moves = max(moves, abs(prefix), diff)
return moves
4. Time and Space Complexity
| Time Complexity | Space Complexity | |
| C++ | O(n) | O(1) |
| Java | O(n) | O(1) |
| JavaScript | O(n) | O(1) |
| Python | O(n) | O(1) |
- The code efficiently balances the machines using a prefix sum and greedy approach.
- It has a linear time complexity and constant space complexity, making it optimal for this problem.