Leetcode 1151 Minimum Swaps to Group All 1's Together

Problem statement

https://leetcode.com/problems/minimum-swaps-to-group-all-1s-together/

Solution

The idea is that we need to put all k ones to adjacent places. We can try all n - k + 1 different places and for each of them check how many ones we miss. It can be quickly done with cumulative sums.

Complexity

Time complexity is O(n), space complexity is O(n) as well to keep cumulative sums.

Code

class Solution:
     def minSwaps(self, data):
         k, n = sum(data), len(data)
         acc = [0] + list(accumulate(data))
         return k - max(acc[i+k] - acc[i] for i in range(n - k + 1))