Interview Pearls: K Consecutive Bit Flips

This is a cool problem that sounds very hard by becomes easy with two intuition sparks (and a little twinkle).

Description

In an array A containing only 0s and 1s, a K-bit flip consists of choosing a (contiguous) subarray of length K 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.

Example

Input: A = [0,0,0,1,0,1,1,0], K = 3
Output: 3

Coding Practice

Try solving this problem before moving on to the solutions. It is available on LeetCode Online Judge: Minimum Number of K Consecutive Bit Flips. Also, as you read through a solution, try implementing it yourself.

LeetCode is my favorite destinations for algorithmic problems. It has 987 problems and counting, with test cases to validate the correctness, as well as computational and memory complexity. There is also a large community discussing different approaches, tips and tricks.

Intuition 1

Just want to share my thought process; I am sure that there is a formal proof somewhere.

1. Since K is fixed, it does not make sense to do the flip for any given index more than once. It's a XOR operation, even flips will be equal to zero flips, odd flips will be equal to one flip. So, there could be up to n - K flips.
2. Since it's a XOR operation, we can do flips in any order.
3. Say we start do flips left to right. That means that, when we encounter zero, we have no choice but flip.

At this point, this intuition is sound enough to try a greedy approach.

Naïve Greedy Solution

Go through the array and flip K elements when encounter zero. Return -1 if you cannot do K flips.

int minKBitFlips(vector<int>& A, int K, int res = 0) {
  for (auto i = 0; i < A.size(); ++i) {
    if (A[i] != 1) {
      if (i + K - 1 >= A.size()) return -1;
      for (auto j = i; j < i + K; ++j) A[j] = !A[j];
      ++res;
    }
  }
  return res;
}

Complexity Analysis

The time complexity of this solution is O(n * K), where n is the length of A. This solution is not accepted by the online judge.

Update: this solution is accepted by OJ with the ~5,000 ms runtime (vs. < 100 ms for the solutions below). So, I could have gotten lucky during the contest!

Intuition 2

Since we are doing XOR operation, even flips will be equal to zero flips, odd flips will be equal to one flip. So, instead of modifying K bits every time we encounter zero, we can just track the current number of flips.

Linear Solution

Here, we are using a queue to track flips. When we 'flip', we put the end index of our flip (i + K - 1) into our queue. The size of the queue will indicate number of flips; we also remove past 'flips' from our queue.

int minKBitFlips(vector<int>& A, int K, int res = 0) {
  queue<int> flips;
  for (auto i = 0; i < A.size(); ++i) {
    if (A[i] != (flips.size() % 2 ? 0 : 1)) {
      ++res;
      flips.push(i + K - 1);
    }
    if (!flips.empty() && flips.front() <= i) flips.pop();
  }
  return flips.empty() ? res : -1;
}

Complexity Analysis

The time complexity of this solution is O(n), and the memory complexity is O(K).

Constant Memory Solution

Instead of using the queue, we can track the total number of flips, and use the source array to mark flips with negative values.

Note that we restore original values after the processing, so the source array is not changed.

int minKBitFlips(vector<int>& A, int K, int res = 0, int flips = 0) {
  for (auto i = 0; i < A.size(); ++i) {
    if (A[i] == flips % 2) {
      if (i > A.size() - K) return -1;
      ++res, ++flips, A[i] -= 2;
    }
    if (i >= K - 1 && A[i - K + 1] < 0) --flips, A[i - K + 1] += 2;
  }
  return res;
}

Complexity Analysis

The time complexity of this solution is O(n), and the memory complexity is O(1).