Super Washing Machines — LeetCode 517 Python Solution

The problem

You have n super washing machines on a line. Initially, each washing machine has some dresses or is empty.

Example

Input

machines = [1,0,5]

Output

3

Explanation

1st move: 1 0 <-- 5 => 1 1 4

Python solution

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

Complexity

Pattern: Greedy

Take the locally best option every time — when you can prove that never costs you later. LeetCode 517. Super Washing Machines is filed here on both counts: the reference solution below belongs to the algorithm family this hub collects, and LeetCode tags it Greedy.

The greedy guide has the Python template for the pattern and the 346 LeetCode problems that use it.

Related problems