DDSA Solutions

995. Minimum Number of K Consecutive Bit Flips

UnknownView on LeetCode
ArrayGreedySliding WindowQueue
Time: O(n)
Space: O(1)

Problem Overview

Greedy left-to-right: when current bit is 0, flip window of size k.

Intuition

Greedy left-to-right: when current bit is 0, flip window of size k. Use difference array to track running flip count in O(n).

Algorithm

  1. 1flipCount running total. delta[] difference array.
  2. 2For each i: flipCount += delta[i]. If (nums[i]+flipCount)%2==0: must flip here. If i+k>n: return -1. Increment flipCount, delta[i+k]--.

Common Pitfalls

  • •Difference array makes tracking O(1) per position. Must flip only when current effective bit is 0.
995.cs
C#
// Approach: Sliding window; mark flip positions in-place using value 2; track running flip parity with a counter.
// Time: O(n) Space: O(1)

public class Solution
{
    public int MinKBitFlips(int[] nums, int k)
    {
        int n = nums.Length, ans = 0, times = 0;

        for (int i = 0; i < n; i++)
        {
            if (i >= k && nums[i - k] == 2)
                times--;

            if (nums[i] == times % 2)
            {
                if (i + k > n)
                    return -1;

                ans++;
                times++;
                nums[i] = 2;
            }
        }

        return ans;
    }
}
Was this solution helpful?

Related Problems