Super Washing Machines

Problem Id: 517 Difficulty: Hard


Intuition

Solution


class Solution:
    def findMinMoves(self, machines: List[int]) -> int:
        n = len(machines)
        s = sum(machines)
        if n == 0 or s % n != 0:
            return -1
        m = s // n
        moves = [0] * (n + 1)
        left = 0
        for i in range(n):
            left += machines[i]
            left -= m
            moves[i + 1] = left
        ans = 0
        for i in range(n):
            if moves[i] < 0 and moves[i + 1] > 0:
                ans = max(
                    abs(moves[i]) + abs(moves[i + 1]),
                    ans
                )
            else:
                ans = max(
                    max(abs(moves[i]), abs(moves[i + 1])),
                    ans
                )
        return ans