Minimum Operations to Make Binary Array Elements Equal to One I

medium array greedy sliding window

Problem

You are given a binary array nums. In one operation you may choose any 3 consecutive elements and flip all of them (0 → 1, 1 → 0). Return the minimum number of operations needed to make every element equal to 1, or -1 if it is impossible.

Inputnums = [0,1,1,1,0,0]

Output3

Flip [0,1,2] → [1,0,0,1,0,0], flip [1,2,3] → [1,1,1,0,0,0], flip [3,4,5] → [1,1,1,1,1,1]. Three flips.

nums (comma-separated 0/1)

def minOperations(nums):
    n = len(nums)
    ops = 0
    # Scan left to right. The leftmost 0 can only be fixed
    # by flipping the window that starts at it.
    for i in range(n - 2):
        if nums[i] == 0:
            nums[i] ^= 1          # flip the 3 consecutive
            nums[i + 1] ^= 1      # elements i, i+1, i+2
            nums[i + 2] ^= 1
            ops += 1
    # The last two elements can no longer be touched.
    if nums[n - 1] == 0 or nums[n - 2] == 0:
        return -1
    return ops

function minOperations(nums) {
  const n = nums.length;
  let ops = 0;
  // Scan left to right. The leftmost 0 can only be fixed
  // by flipping the window that starts at it.
  for (let i = 0; i <= n - 3; i++) {
    if (nums[i] === 0) {
      nums[i] ^= 1;          // flip the 3 consecutive
      nums[i + 1] ^= 1;      // elements i, i+1, i+2
      nums[i + 2] ^= 1;
      ops++;
    }
  }
  // The last two elements can no longer be touched.
  if (nums[n - 1] === 0 || nums[n - 2] === 0) return -1;
  return ops;
}

int minOperations(int[] nums) {
    int n = nums.length;
    int ops = 0;
    // Scan left to right. The leftmost 0 can only be fixed
    // by flipping the window that starts at it.
    for (int i = 0; i <= n - 3; i++) {
        if (nums[i] == 0) {
            nums[i] ^= 1;          // flip the 3 consecutive
            nums[i + 1] ^= 1;      // elements i, i+1, i+2
            nums[i + 2] ^= 1;
            ops++;
        }
    }
    // The last two elements can no longer be touched.
    if (nums[n - 1] == 0 || nums[n - 2] == 0) return -1;
    return ops;
}

int minOperations(vector<int>& nums) {
    int n = nums.size();
    int ops = 0;
    // Scan left to right. The leftmost 0 can only be fixed
    // by flipping the window that starts at it.
    for (int i = 0; i <= n - 3; i++) {
        if (nums[i] == 0) {
            nums[i] ^= 1;          // flip the 3 consecutive
            nums[i + 1] ^= 1;      // elements i, i+1, i+2
            nums[i + 2] ^= 1;
            ops++;
        }
    }
    // The last two elements can no longer be touched.
    if (nums[n - 1] == 0 || nums[n - 2] == 0) return -1;
    return ops;
}

Explanation

This is a greedy left-to-right sweep. Think about the very first element. If nums[0] is already 1 we leave it alone. If it is 0, the only window that contains index 0 is the one starting at index 0 (indices 0, 1, 2). So to fix index 0 we are forced to flip that window. There is no other choice.

Once index 0 is a 1, we never want to touch it again — any later window that included it would break it. So we move on and apply the exact same reasoning to index 1, then index 2, and so on. Each position, when we reach it, is decided permanently: if it is 0 we flip the window anchored at it; otherwise we skip.

Because every flip is forced, the count we accumulate is provably the minimum — no shorter sequence of operations can exist.

The sweep can only anchor a window at indices 0 … n-3, since a window needs three cells. After the sweep the last two cells nums[n-2] and nums[n-1] can never be changed again. If either of them is still 0, the array is impossible to finish and we return -1.

Example: [0,1,1,1,0,0]. We flip at index 0, then index 3, then... index 3's flip turns indices 3,4,5 into 1s on the third anchor, giving 3 operations and an all-ones array. For [0,1,1,1] the single flip at index 0 leaves [1,0,0,1], and the trailing 0s can no longer be reached, so the answer is -1.

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