Problem statement

https://leetcode.com/problems/super-washing-machines/

Solution

Quite misleading statement. For example for [2, 0, 0, 2] the answer is 1, because we can choose m not adjacent machines.

Let us first normalize our machines: subtract average from all of them, so now we need to make all number equal to zero. Let us evaluate cumulative sums of normalized array. Then we can have an estimate:

  1. We need at least maximum of absolute values of this cumulative sum to get all zeros. Why? Because on each iteration we can change this sum only by one: for example we have [-4, -4, 7, 1], then we have [-4,-4], [7,1] as one of split of data: we need at least 8 moves to make right part equal to 0.
  2. We need at least maximum of absolute values of normalized machines. Why, again, because for example for [-2, 5, -3] we need at least $5$ steps to make all numbers equal to zero.
  3. It can be proves, that these two conditions are enough, so we can create example as well, which is a quite painful to prove in fact.

Complexity

Time complexity is O(n), space complexity for my code is O(n), which can be reduced to O(1).

Code

class Solution:
    def findMinMoves(self, machines):
        sum_m, len_m = sum(machines), len(machines)
        if sum_m % len_m != 0: return -1
        norm_mach = [m - sum_m//len_m for m in machines]
        return max(max([abs(i) for i in accumulate(norm_mach)]), max(norm_mach))