3.38 Minimum Operations to Make Binary Array Elements Equal to One I

3.38.1 Problem Metadata

3.38.2 Description

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

3.38.3 Examples

Example 1:

Input: nums = [0,1,1,1,0,0]
Output: 3
Explanation: We can do the following operations:
- Choose the elements at indices 0, 1 and 2. The resulting array is nums = [1,0,0,1,0,0].
- Choose the elements at indices 1, 2 and 3. The resulting array is nums = [1,1,1,0,0,0].
- Choose the elements at indices 3, 4 and 5. The resulting array is nums = [1,1,1,1,1,1].

Example 2:

Input: nums = [0,1,1,1]
Output: -1
Explanation: It is impossible to make all elements equal to 1.

3.38.4 Constraints

  • 3 <= nums.length <= 10^5
  • 0 <= nums[i] <= 1

3.38.5 Solution - Greedy Sequential Traversal

3.38.5.1 Walkthrough

Greedy left-to-right: once you pass index i, you can never change nums[i] again except by flipping a window that starts at i. Therefore, if nums[i] is 0, you must flip window [i, i+1, i+2] immediately to lock it to 1 and move on. After processing through len-3, only the final two positions remain; if either is 0, the task is impossible.

3.38.5.2 Analysis

  • Time Complexity: O(n) — single pass
  • Space Complexity: O(1) — in-place flips plus a counter
  • Notes: Early-continue when nums[i] == 1; use XOR (^= 1) to flip neighbors.

3.38.5.3 Implementation Steps

  1. Set count = 0.
  2. For i from 0 to len - 3:
    • If nums[i] == 0, flip nums[i], nums[i+1], nums[i+2] (use XOR for neighbors) and increment count.
  3. After the loop, if either of the last two elements is 0, return -1; otherwise return count.

3.38.6 Java Code

class Solution {
    public int minOperations(int[] nums) {
        int count = 0;
        int len = nums.length;
        for(int i = 0; i < len - 2; i++) {
            if(nums[i] == 1)
                continue;
            // Use XOR(^) to flip
            nums[i] = 1;
            nums[i+1] ^= 1;
            nums[i+2] ^= 1;
            count++;
        }
        // check if the last two bits are 1, nums[len-3] is already 1
        if(nums[len-1] == 0 || nums[len-2] == 0) {
            return -1;
        }
        return count;
    }
}