995. Minimum Number of K Consecutive Bit Flips

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 1:

Input: nums = [0,1,0], k = 1
Output: 2
Explanation: Flip nums[0], then flip nums[2].

Example 2:

Input: nums = [1,1,0], k = 2
Output: -1
Explanation: No matter how we flip subarrays of size 2, we cannot make the array become [1,1,1].

Example 3:

Input: nums = [0,0,0,1,0,1,1,0], k = 3
Output: 3
Explanation:
Flip nums[0],nums[1],nums[2]: nums becomes [1,1,1,1,0,1,1,0]
Flip nums[4],nums[5],nums[6]: nums becomes [1,1,1,1,1,0,0,0]
Flip nums[5],nums[6],nums[7]: nums becomes [1,1,1,1,1,1,1,1]

Constraints:

• 1 <= nums.length <= 105
• 1 <= k <= nums.length

Approach 01:

class Solution {
public:
    int minKBitFlips(vector<int>& nums, int k) {
        int flips_needed = 0;
        int current_flips = 0;

        for (int i = 0; i < nums.size(); ++i) {
            if (i >= k && nums[i - k] == 2)
                --current_flips;
            if (current_flips % 2 == nums[i]) {
                if (i + k > nums.size())
                    return -1;
                ++flips_needed;
                ++current_flips;
                nums[i] = 2;
            }
        }

        return flips_needed;
    }
};

from typing import List


class Solution:
    def minKBitFlips(self, nums: List[int], k: int) -> int:
        flips_needed = 0
        current_flips = 0

        for i in range(len(nums)):
            if i >= k and nums[i - k] == 2:
                current_flips -= 1
            if current_flips % 2 == nums[i]:
                if i + k > len(nums):
                    return -1
                flips_needed += 1
                current_flips += 1
                nums[i] = 2

        return flips_needed

Time Complexity:

• Iterating Through All Elements: \( O(n) \)
  • We iterate through each element of the input list nums exactly once. This is a single loop that runs for \( n \) iterations, where \( n \) is the length of the list.
  • Inside the loop, we perform constant time operations: checking conditions, updating counters, and modifying elements of the list. Each of these operations takes \( O(1) \) time.
• Overall Time Complexity: \( O(n) \)

Since the loop runs \( n \) times and each iteration involves \( O(1) \) operations, the total time complexity is \( O(n) \).

Space Complexity:

• Variables flips_needed and current_flips: \( O(1) \)

We use a few extra variables to keep track of the number of flips needed and the current number of flips. These variables do not depend on the size of the input list, so they take constant space.

• In-place Modification of Input List nums: \( O(1) \)

We modify the input list nums in-place by marking flipped elements with a special value (2). This does not require additional space proportional to the size of the input.

• Overall Space Complexity: \( O(1) \)

Since we are only using a constant amount of extra space (not dependent on the input size), the overall space complexity is \( O(1) \).