🎨Now live: Try our Free AI Image Generation Feature

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
- Initialize a counter
res
to count the number of operations. - Iterate through the array from the beginning to
n-3
(wheren
is the length of the array): - If the current element is0
, flip it and the next two elements. Increment the counterres
. - After the loop, check if the last two elements are both
1
. If they are, return the counterres
. Otherwise, return-1
as it is not possible to make all elements1
.
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;
}
}