3675.minimum-swaps-to-group-all-1s-together.py

#  Tag: Sliding Window, Array
#  Time: O(N)
#  Space: O(1)
#  Ref: Leetcode-1151
#  Note: -

#  In this problem there is a binary array (contains only 0 and 1).
#  You can swap arbitrary elements of the array.
#  
#  Now you need to combine all 1s in the array.
#  Returns the minimum number of swaps required for a combination.
#  
#  **Example 1**
#  
#  Input：
#  
#  ```plaintext
#  [1,0,1,0,1]
#  ```
#  
#  Explanation:
#  
#  `[1,1,1,0,0]` or `[0,0,1,1,1]` only need one swap.
#  
#  Output:
#  
#  ```plaintext
#  1
#  ```
#  
#  **Example 2**
#  
#  Input:
#  
#  ```plaintext
#  [1,0,1,0,1,0,1,1,0,1]
#  ```
#  
#  Output:
#  
#  ```plaintext
#  2
#  ```
#  
#  Explanation:
#  
#  `[0,0,0,0,1,1,1,1,1,1]` requires only two swaps.
#  
#  

from typing import (
    List,
)

class Solution:
    """
    @param arr: the binary array
    @return: the minimal number of  swaps
    """
    def min_swaps(self, arr: List[int]) -> int:
        # write your code here
        n = len(arr)
        k = arr.count(1)
        ones = 0
        count = 0
        for i in range(n):
            if i >= k:
                count -= arr[i - k]

            count += arr[i]
            if i >= k - 1:
                ones = max(ones, count)
                
        return k - ones