Problem statement

https://binarysearch.com/problems/Adjacent-Swaps-to-Group-Ones/

Solution

It is special case of problem Leetcode 1703. Minimum Adjacent Swaps for K Consecutive Ones. The idea is to look at indexes where we have 1, then we need to answer the question: we need to choose window of size k and evaluate value that has minimum distance to their median sequence. In this problem in fact we have only one option to choose window.

Complexity

It is O(n) for time and space.

Code

class Solution:
    def solve(self, A):
        A = [i for i, a in enumerate(A) if a == "1"]
        n = len(A)
        B = [0] + list(accumulate(A))
        return B[n] - B[n//2] - B[(n+1)//2] - B[0] - (n // 2) * ((n + 1) // 2)