Minimum Number of K Consecutive Bit Flips

HardArrayBit ManipulationQueueSliding WindowPrefix Sum

Solution

export function minKBitFlips(nums: number[], k: number): number {
  const n = nums.length;
  const isFlipped = new Array(n).fill(0);
 
  let answer = 0;
  let flipped = 0;
  for (let i = 0; i < n; i++) {
    if (k <= i) {
      flipped ^= isFlipped[i - k];
    }
    if (flipped === nums[i]) {
      if (n < i + k) {
        return -1;
      }
      isFlipped[i] = 1;
      flipped ^= 1;
      answer += 1;
    }
  }
  return answer;
}

Complexity

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