3191. Minimum Operations to Make Binary Array Elements Equal to One I

Intuition

The problem requires us to flip any three consecutive elements in a binary array to eventually make all elements equal to 1. Each flip operation will affect three consecutive elements, making this a non-trivial task where a greedy approach can be effective.

The primary intuition is to scan the array from left to right and whenever a 0 is encountered, we flip the current element and the next two elements. This approach ensures that we turn the current element to 1 while trying to minimize the number of flips.

Approach

1. Initialize a counter res to count the number of operations.
2. Iterate through the array from the beginning to n-3 (where n is the length of the array): - If the current element is 0, flip it and the next two elements. Increment the counter res.
3. After the loop, check if the last two elements are both 1. If they are, return the counter res. Otherwise, return -1 as it is not possible to make all elements 1.

This approach ensures that we handle every 0 in the array efficiently, and it respects the condition that only three consecutive elements can be flipped at a time.

Complexity

• Time Complexity: O(n) We iterate through the array once, performing a constant-time operation for each element.
• Space Complexity: O(1) The algorithm uses a fixed amount of extra space regardless of the input size.

Code

C++

class Solution {
public:
    int minOperations(vector& nums) {
        int res = 0;
        int n = nums.size();

        for (int i = 0; i < n - 2; ++i) {
            if (nums[i] == 0) {
                nums[i] = 1;
                nums[i + 1] = nums[i + 1] ? 0 : 1;
                nums[i + 2] = nums[i + 2] ? 0 : 1;
                ++res;
            }
        }

        return nums[n - 1] && nums[n - 2] ? res : -1;
    }
};

Python

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

        for i in range(n - 2):
            if nums[i] == 0:
                nums[i] = 1
                nums[i + 1] = 0 if nums[i + 1] == 1 else 1
                nums[i + 2] = 0 if nums[i + 2] == 1 else 1
                res += 1

        return res if nums[n - 1] == 1 and nums[n - 2] == 1 else -1

Java

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

        for (int i = 0; i < n - 2; ++i) {
            if (nums[i] == 0) {
                nums[i] = 1;
                nums[i + 1] = nums[i + 1] == 1 ? 0 : 1;
                nums[i + 2] = nums[i + 2] == 1 ? 0 : 1;
                ++res;
            }
        }

        return nums[n - 1] == 1 && nums[n - 2] == 1 ? res : -1;
    }
}

JavaScript

/**
 * @param {number[]} nums
 * @return {number}
 */
var minOperations = function (nums) {
  var res = 0;
  var n = nums.length;
  for (var i = 0; i < n - 2; ++i) {
    if (nums[i] === 0) {
      nums[i] = 1;
      nums[i + 1] = nums[i + 1] ? 0 : 1;
      nums[i + 2] = nums[i + 2] ? 0 : 1;
      ++res;
    }
  }
  return nums[n - 1] && nums[n - 2] ? res : -1;
};

Go

func minOperations(nums []int) int {
    res := 0
    n := len(nums)
    for i := 0; i < n-2; i++ {
        if nums[i] == 0 {
            nums[i] = 1
            if nums[i+1] == 1 {
                nums[i+1] = 0
            } else {
                nums[i+1] = 1
            }
            if nums[i+2] == 1 {
                nums[i+2] = 0
            } else {
                nums[i+2] = 1
            }
            res++
        }
    }
    if nums[n-1] == 1 && nums[n-2] == 1 {
        return res
    } else {
        return -1
    }
}

C#

public class Solution {
    public int MinOperations(int[] nums) {
        int res = 0;
        int n = nums.Length;

        for (int i = 0; i < n - 2; ++i) {
            if (nums[i] == 0) {
                nums[i] = 1;
                nums[i + 1] = nums[i + 1] == 1 ? 0 : 1;
                nums[i + 2] = nums[i + 2] == 1 ? 0 : 1;
                ++res;
            }
        }

        return nums[n - 1] == 1 && nums[n - 2] == 1 ? res : -1;
    }
}