Problem

You are given a binary array nums.

You can do the following operation on the array any number of times (possibly zero):

  • Choose any 3 consecutive elements from the array and flip all of them.

Flipping an element means changing its value from 0 to 1, and from 1 to 0.

Return the minimum number of operations required to make all elements in nums equal to 1. If it is impossible, return -1.

Examples

Example 1:

1
2
3
4
5
6
7

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:

1
2
3
4

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

Constraints:

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

Solution

Method 1 - Greedy

Here is the approach:

  1. Use a greedy strategy to process the array from left to right. Start flipping at the first occurrence of 0 because flipping is only needed if an element is 0.
  2. Each flip can affect up to three consecutive elements. Therefore:
    • When encountering a 0 at position i, flip elements at positions i, i+1, and i+2.
    • If i+2 exceeds the boundary of the array (i.e., not enough elements for a complete flip), transformation becomes impossible, and return -1.
  3. After processing the entire array, verify if all elements in nums are 1. If not, return -1.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

class Solution {
    public int minOperations(int[] nums) {
        int n = nums.length;
        int ans = 0;

        for (int i = 0; i <= n - 3; i++) {  // Loop till n-3 because flip affects i, i+1, i+2
            if (nums[i] == 0) {
                // Flip nums[i], nums[i+1], nums[i+2]
                nums[i] ^= 1;
                nums[i + 1] ^= 1;
                nums[i + 2] ^= 1;
                ans++;
            }
        }
        
        // Post-loop check
        for (int val : nums) {
            if (val == 0) {
                return -1; // If any `0` remains, return -1
            }
        }
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

class Solution:
    def minOperations(self, nums: List[int]) -> int:
        n: int = len(nums)
        ans: int = 0

        for i in range(n - 2):  # Loop until n-3 because flipping affects i, i+1, i+2
            if nums[i] == 0:
                # Flip nums[i], nums[i+1], nums[i+2]
                nums[i] ^= 1
                nums[i + 1] ^= 1
                nums[i + 2] ^= 1
                ans += 1
        
        # Post-loop check
        if all(x == 1 for x in nums):
            return ans
        return -1

Complexity

  • ⏰ Time complexity: O(n), where n is the size of the array. The array is traversed once, flipping elements when necessary.
  • 🧺 Space complexity: O(1). No extra space is used; modifications are made in-place.