Problem of The Day: Minimum Number of K Consecutive Bit Flips

Problem Statement

Brute Force - TLE

class Solution:
    def minKBitFlips(self, nums: List[int], k: int) -> int:
        n = len(nums)
        def dfs(i, curr):
            if i + k > n:
                if all(curr):
                    return 0
                return float('inf')

            skip = dfs(i + 1, curr[:])
            for j in range(i, i + k):
                curr[j] = int(not curr[j])
            flip = dfs(i + 1, curr[:]) + 1
            return min(skip, flip)
        res = dfs(0, nums[:])
        if res == float('inf'):
            return -1
        return res

Editorial

class Solution:
    def minKBitFlips(self, nums: List[int], k: int) -> int:
        current_flips = 0  # Tracks the current number of flips
        total_flips = 0  # Tracks the total number of flips

        for i in range(len(nums)):
            # If the window slides out of the range and the leftmost element is
            #  marked as flipped (2), decrement current_flips
            if i >= k and nums[i - k] == 2:
                current_flips -= 1

            # Check if the current bit needs to be flipped
            if (current_flips % 2) == nums[i]:
                # If flipping would exceed array bounds, return -1
                if i + k > len(nums):
                    return -1
                # Mark the current bit as flipped
                nums[i] = 2
                current_flips += 1
                total_flips += 1

        return total_flips

• time: O(n)
• space: O(n)