995. Minimum Number of K Consecutive Bit Flips

Problem Statement

link: LeetCode.cn LeetCode

You are given a binary array nums and an integer k.

A k-bit flip is choosing a subarray of length k from nums and simultaneously changing every 0 in the subarray to 1, and every 1 in the subarray to 0.

Return the minimum number of k-bit flips required so that there is no 0 in the array. If it is not possible, return -1.

A subarray is a contiguous part of an array.

Example:

Input: nums = [0,1,0], k = 1 Output: 2

Input: nums = [1,1,0], k = 2 Output: -1

Input: nums = [0,0,0,1,0,1,1,0], k = 3 Output: 3

Solution Approach

The algorithm maintains a sliding window using a deque to keep track of the indices of the bits to flip. It iterates through the array, flipping bits as necessary, and returns the count of flips required or -1 if it’s not possible.

Algorithm

1. Maintain Sliding Window: Use a deque q to track indices for bits to flip. Remove indices outside the current window.
2. Check and Flip Bits: If the deque size modulo 2 matches the current bit, flip bits and count. Return -1 if flipping extends beyond array bounds.
3. Return Result: Return the count of flips required.

Implement

    class Solution:
      def minKBitFlips(self, nums: List[int]) -> int:
          n = len(nums)
          q = collections.deque()
          res = 0
          for i in range(n):
              if q and i >= q[0] + k:
                  q.popleft()
              if len(q) % 2 == nums[i]:
                  if i + k > n:
                      return -1
                  q.append(-1)
                  res += 1
          return res
          
    
      

    
    

Twitter  facebook  Email