995. Minimum Number of K Consecutive Bit Flips

Intuition

The problem requires us to flip subarrays of length k in such a way that all elements in the binary array nums are converted to 1. So we can start from the leftmost and using a sliding window to flip as soon as we encounter a 0 that needs to be turned into 1.

Approach 1: Using a Queue

This approach uses a queue to efficiently manage the flips in a sliding window.

Explanation:

1. Initialization:
2. n: The size of the input array nums.
3. count: A counter to keep track of the number of k-bit flips performed.
4. state: A boolean flag to represent the current flip state (0 means no flip, 1 means flipped).
5. q: A queue to keep track of the end indices of the k-bit flip segments.
6. Traversing the Array:
7. Iterate over each element in the array nums using a for loop.
8. Checking and Flipping:
9. Condition to Flip: If the current element nums[i] is equal to the state (indicating it needs to be flipped to become 1):
   • Check if flipping a subarray of length k starting at index i would exceed the bounds of the array. If so, return -1 as it is impossible to flip the required subarray.
   • If within bounds, increment the count of flips.
   • Toggle the state to indicate a new flip segment has started.
   • Push the end index of the current flip segment (i + k - 1) into the queue.
10. Maintaining the Flip State:
11. After processing the current element, check if there are any flip segments in the queue whose end index is equal to the current index i.
12. If so, this means the effect of the flip segment ends at the current index. Toggle the state back and pop the end index from the queue.
13. Returning the Result:
14. After traversing the entire array, return the total count of k-bit flips performed.

Complexity

• Time complexity: O(n)
• Space complexity: O(k)

Code

class Solution {
public:
    int minKBitFlips(vector<int>& nums, int k) {
        int n = nums.size(), count = 0;
        bool state = 0;
        queue<int> q;

        for (int i = 0; i < n; i++) {
            if (nums[i] == state) {
                if (i + k > n) return -1;

                ++count;
                state ^= 1;
                q.push(i + k - 1);
            }

            if (!q.empty() && q.front() == i) {
                state ^= 1;
                q.pop();
            }
        }

        return count;
    }
};

Approach 2: In-place Modification

Instead of using a queue, we can modify the input array in place to save memory

Explanation:

1. Initialization:
2. n: The size of the input array nums.
3. count: A counter to keep track of the number of k-bit flips performed.
4. state: A boolean flag to represent the current flip state (0 means no flip, 1 means flipped).
5. Traversing the Array:
6. Iterate over each element in the array nums using a for loop.
7. Checking and Flipping:
8. Condition to Flip: If the current element nums[i] is equal to the state (indicating it needs to be flipped to become 1):
   • Check if flipping a subarray of length k starting at index i would exceed the bounds of the array. If so, return -1 as it is impossible to flip the required subarray.
   • If within bounds, increment the count of flips.
   • Toggle the state to indicate a new flip segment has started.
   • Mark the start of the flip at nums[i] by XOR-ing nums[i] with -1. This effectively flips all the bits of nums[i].
9. Maintaining the Flip State:
10. Check for Ending Flips: When i - k + 1 >= 0, it means the flip effect (if any) from i - k + 1 is ending.
    • If nums[i - k + 1] is less than 0, it means this position marked the start of a flip.
    • Toggle the state back.
    • (Optional) Reset nums[i - k + 1] by XOR-ing it with -1 to remove the mark.
11. Returning the Result:
12. After traversing the entire array, return the total count of k-bit flips performed.

Complexity

• Time complexity: O(n)
• Space complexity: O(1)

Code

class Solution {
public:
    int minKBitFlips(vector<int>& nums, int k) {
        int n = nums.size(), count = 0;
        bool state = 0;

        for (int i = 0; i < n; i++) {
            if (nums[i] == state) {
                if (i + k > n) return -1;

                ++count;
                state ^= 1;
                nums[i] ^= -1;
            }

            if (i - k + 1 >= 0 && nums[i - k + 1] < 0) {
                state ^= 1;
                nums[i - k + 1] ^= -1;
            }
        }

        return count;
    }
};

Approach 3:

1.Initialize Variables:

• flippedTime to track the number of flips that affect the current position.
• cnt to count the total number of flips performed.

2.Iterate through nums:

• For each element i in nums , if i is greater than or equal to k and the element k positions before was a flip (marked by 2), reduce flippedTime because that flip no longer affects the current window.
• If the current element, considering flippedTime, need to be flipped (flippedTime % 2 == nums[i]), check if it's possible to flip the next k elements
• If i + k exceeds the array bounds , return -1.
• Otherwise, increment cnt, flippedTime, and mark the current position with 2.

3.Return the result:

• If the loop completes, return cnt the count of flips.

Complexity

• Time complexity: O(N)
• Space complexity: O(1)

Code

class Solution {
public:
    int minKBitFlips(vector<int>& nums, int k) {
        int flippedTime = 0, cnt = 0;
        for (int i = 0; i < nums.size(); ++i) {
            if (i >= k && nums[i - k] == 2)
                --flippedTime;
            if (flippedTime % 2 == nums[i]) {
                if (i + k > nums.size())
                    return -1;
                ++cnt;
                ++flippedTime;
                nums[i] = 2;
            }
        }
        return cnt;
    }
};