Minimum Operations to Make Binary Array Elements Equal to One I solution and explanation
Google
9 more videos on this problem
Minimum Operations to Make Binary Array Elements Equal to One I - Leetcode 3191 - PythonNeetCodeIO · 8:41 · 9K views
Minimum Operations to Make Binary Array Elements Equal to One I | Leetcode 3191Techdose · 7:39 · 5K views
3191. Minimum Operations to Make Binary Array Elements Equal to One I | leetcode daily challenge dsaShashCode · 7:28 · 2K views
3191. Minimum Operations to Make Binary Array Elements Equal to One I (Leetcode Medium)Programming Live with Larry · 5:22 · 808 views
LeetCode 3191 | Minimum Operations to Make Binary Array Elements Equal to One I | #leetcodecontestAlgo Horizon · 10:34 · 675 views
🔥 3191. Minimum Operations to Make Binary Array Elements Equal to One | POTD | Explained with proof🔥codeIT · 7:41 · 161 views
3191. Minimum Operations to Make Binary Array Elements Equal to One I | Leetcode | biweekly 133Brute force · 5:03 · 103 views
3191. Minimum Operations to Make Binary Array Elements Equal to One I | Leetcode Python SolutionsStatLearn Tech · 9:49 · 49 views
Leetcode 3191 |Minimum Operations to Make Binary Array Elements Equal to One ICode Plus · 2:05 · 42 views
Minimum Operations to Make Binary Array Elements Equal to One I | LeetCode 3191 | Developer CoderDeveloper Coder · 7:28 · 41 views
The 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.
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.
Constraints:
3 <= nums.length <= 1050 <= nums[i] <= 1
Approach overview
Problem Overview: You receive a binary array and an operation that flips exactly three consecutive elements (0 becomes 1 and 1 becomes 0). The goal is to apply the minimum number of operations so every element becomes 1. If it is impossible, return -1.
Approach 1: Greedy Left-to-Right Flipping (O(n) time, O(1) space)
Scan the array from left to right and fix problems immediately. When you encounter a 0 at index i, the only way to make it 1 is to flip the subarray [i, i+1, i+2]. Perform the flip, increment the operation count, and continue scanning. This greedy rule works because once you move past index i, you can never affect it again. If you reach the final two indices and still see a 0, no valid 3-length operation can fix it, so the answer is -1. This approach modifies the array in place and relies on simple iteration over the array.
Approach 2: Sliding Window with Reversal Tracking (O(n) time, O(n) space)
Instead of physically flipping elements, track whether each position is logically flipped by previous operations. Maintain a running count of active flips affecting the current index using a queue or prefix-style tracking. When the parity of flips makes the current value effectively 0, start a new flip window at that index and record that the flip effect will expire after three positions. This technique avoids repeated bit updates and models flips using window boundaries, similar to problems that use sliding window or prefix sum style difference tracking. It is especially useful when operations affect ranges and you want constant-time updates per index.
Recommended for interviews: The greedy approach is what most interviewers expect first. It directly models the constraint that each index must be fixed the moment you see it. Explaining why earlier indices cannot be revisited demonstrates good reasoning. The sliding window tracking approach shows deeper understanding of range operations and optimization techniques, which often appears in problems involving bit manipulation or repeated flips.
Approach 1: Greedy Approach
The key idea in this approach is to perform 'flipping' operations whenever we encounter a 0. We ensure that once a segment of three elements is flipped, any subsequent operations are impacted correctly. The goal is to handle flipping from left to right, ensuring that segments with 0's at the beginning are flipped first to maximize the chance of turning all elements to 1.
def min_flips(nums):
flips = 0
for i in range(len(nums) - 2):
if nums[i] == 0:
flips += 1
nums[i] ^= 1
nums[i + 1] ^= 1
nums[i + 2] ^= 1
if any(x == 0 for x in nums[-3:]):
return -1
return flips
nums = [0, 1, 1, 1, 0, 0]
print(min_flips(nums))public class MinFlips {
public static int minFlips(int[] nums) {
int flips = 0;
for (int i = 0; i <= nums.length - 3; ++i) {
if (nums[i] == 0) {
flips++;
nums[i] ^= 1;
nums[i + 1] ^= 1;
nums[i + 2] ^= 1;
}
}
for (int i = nums.length - 3; i < nums.length; ++i) {
if (nums[i] == 0) return -1;
}
return flips;
}
public static void main(String[] args) {
int[] nums = {0, 1, 1, 1, 0, 0};
System.out.println(minFlips(nums));
}
}#include <vector>
#include <iostream>
int minFlips(std::vector<int>& nums) {
int flips = 0;
for (int i = 0; i <= nums.size() - 3; ++i) {
if (nums[i] == 0) {
flips++;
nums[i] ^= 1;
nums[i + 1] ^= 1;
nums[i + 2] ^= 1;
}
}
for (int i = nums.size() - 3; i < nums.size(); ++i) {
if (nums[i] == 0) return -1;
}
return flips;
}
int main() {
std::vector<int> nums = {0, 1, 1, 1, 0, 0};
std::cout << minFlips(nums) << std::endl;
return 0;
}function minFlips(nums) {
let flips = 0;
for (let i = 0; i <= nums.length - 3; i++) {
if (nums[i] === 0) {
flips++;
nums[i] ^= 1;
nums[i + 1] ^= 1;
nums[i + 2] ^= 1;
}
}
for (let i = nums.length - 3; i < nums.length; i++) {
if (nums[i] === 0) return -1;
}
return flips;
}
let nums = [0, 1, 1, 1, 0, 0];
console.log(minFlips(nums));#include <stdio.h>
#include <stdbool.h>
int minFlips(int* nums, int numsSize) {
int flips = 0;
for (int i = 0; i <= numsSize - 3; ++i) {
if (nums[i] == 0) {
flips++;
nums[i] ^= 1;
nums[i + 1] ^= 1;
nums[i + 2] ^= 1;
}
}
for (int i = numsSize - 3; i < numsSize; ++i) {
if (nums[i] == 0) return -1;
}
return flips;
}
int main() {
int nums[] = {0, 1, 1, 1, 0, 0};
int result = minFlips(nums, 6);
printf("%d\n", result);
return 0;
}using System;
public class MinFlips {
public static int MinFlipsMethod(int[] nums) {
int flips = 0;
for (int i = 0; i <= nums.Length - 3; ++i) {
if (nums[i] == 0) {
flips++;
nums[i] ^= 1;
nums[i + 1] ^= 1;
nums[i + 2] ^= 1;
}
}
for (int i = nums.Length - 3; i < nums.Length; ++i) {
if (nums[i] == 0) return -1;
}
return flips;
}
public static void Main(string[] args) {
int[] nums = {0, 1, 1, 1, 0, 0};
Console.WriteLine(MinFlipsMethod(nums));
}
}Implementation detail: In Python, the flipping and counting procedures are identically applied as in other languages with list mutability leveraged to allow for seamless in-place updation. The solution directly checks for any residual 0s in the last three elements.
Time Complexity: O(n).
Space Complexity: O(1).
Approach 2: Sliding Window with Reversal Tracking
This method uses a sliding window approach to track the range of elements that might affect the result of operations optimally. By maintaining an indicator to denote whether we need a conversion for a specific window position, we can achieve the same goal without changing the original array until necessary or proven feasible.
def min_flips_sliding_window(nums):
flips = need_flip = 0
for i in range(len(nums) - 2):
if (nums[i] + need_flip) % 2 == 0:
need_flip ^= 1
flips += 1
if any((nums[i] + need_flip) % 2 == 0 for i in range(len(nums) - 3, len(nums))):
return -1
return flips
nums = [0, 1, 1, 1, 0, 0]
print(min_flips_sliding_window(nums))public class MinFlipsSlidingWindow {
public static int minFlipsSlidingWindow(int[] nums) {
int flips = 0, need_flip = 0;
for (int i = 0; i <= nums.length - 3; ++i) {
if ((nums[i] + need_flip) % 2 == 0) {
need_flip ^= 1;
++flips;
}
}
for (int i = nums.length - 3; i < nums.length; ++i) {
if ((nums[i] + need_flip) % 2 == 0) return -1;
}
return flips;
}
public static void main(String[] args) {
int[] nums = {0, 1, 1, 1, 0, 0};
System.out.println(minFlipsSlidingWindow(nums));
}
}#include <vector>
#include <iostream>
int minFlipsSlidingWindow(std::vector<int>& nums) {
int flips = 0, need_flip = 0;
for (int i = 0; i <= nums.size() - 3; ++i) {
if ((nums[i] + need_flip) % 2 == 0) {
need_flip ^= 1;
++flips;
}
}
for (int i = nums.size() - 3; i < nums.size(); ++i) {
if ((nums[i] + need_flip) % 2 == 0) return -1;
}
return flips;
}
int main() {
std::vector<int> nums = {0, 1, 1, 1, 0, 0};
std::cout << minFlipsSlidingWindow(nums) << std::endl;
return 0;
}function minFlipsSlidingWindow(nums) {
let flips = 0, needFlip = 0;
for (let i = 0; i <= nums.length - 3; i++) {
if ((nums[i] + needFlip) % 2 === 0) {
needFlip ^= 1;
flips++;
}
}
for (let i = nums.length - 3; i < nums.length; i++) {
if ((nums[i] + needFlip) % 2 === 0) return -1;
}
return flips;
}
let nums = [0, 1, 1, 1, 0, 0];
console.log(minFlipsSlidingWindow(nums));#include <stdio.h>
#include <stdbool.h>
int minFlipsSlidingWindow(int* nums, int numsSize) {
int flips = 0, need_flip = 0;
for (int i = 0; i <= numsSize - 3; ++i) {
if ((nums[i] + need_flip) % 2 == 0) {
need_flip ^= 1;
++flips;
}
}
for (int i = numsSize - 3; i < numsSize; ++i) {
if ((nums[i] + need_flip) % 2 == 0) return -1;
}
return flips;
}
int main() {
int nums[] = {0, 1, 1, 1, 0, 0};
printf("%d\n", minFlipsSlidingWindow(nums, 6));
return 0;
}using System;
public class MinFlipsSlidingWindow {
public static int MinFlipsSlidingWindowMethod(int[] nums) {
int flips = 0, needFlip = 0;
for (int i = 0; i <= nums.Length - 3; ++i) {
if ((nums[i] + needFlip) % 2 == 0) {
needFlip ^= 1;
++flips;
}
}
for (int i = nums.Length - 3; i < nums.Length; ++i) {
if ((nums[i] + needFlip) % 2 == 0) return -1;
}
return flips;
}
public static void Main(string[] args) {
int[] nums = {0, 1, 1, 1, 0, 0};
Console.WriteLine(MinFlipsSlidingWindowMethod(nums));
}
}Implementation detail: This implementation uses Python's inherent dynamic management of list and logical operations, employing a need_flip toggle to ascertain validity of positions and the eventual flip total required to meet all conditions.
Time Complexity: O(n).
Space Complexity: O(1).
Approach 3: Sequential Traversal + Simulation
We notice that the first position in the array that is 0 must undergo a flip operation, otherwise, it cannot be turned into 1. Therefore, we can sequentially traverse the array, and each time we encounter 0, we flip the next two elements and accumulate one operation count.
After the traversal, we return the answer.
The time complexity is O(n), where n is the length of the array nums. The space complexity is O(1).
function minOperations(nums: number[]): number {
const n = nums.length;
let ans = 0;
for (let i = 0; i < n; ++i) {
if (nums[i] === 0) {
if (i + 2 >= n) {
return -1;
}
nums[i + 1] ^= 1;
nums[i + 2] ^= 1;
++ans;
}
}
return ans;
}func minOperations(nums []int) (ans int) {
for i, x := range nums {
if x == 0 {
if i+2 >= len(nums) {
return -1
}
nums[i+1] ^= 1
nums[i+2] ^= 1
ans++
}
}
return
}Complexity comparison
| Approach | Complexity |
|---|---|
| Greedy Approach | Time Complexity: O(n). |
| Sliding Window with Reversal Tracking | Time Complexity: O(n). |
| Sequential Traversal + Simulation | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Greedy Left-to-Right Flip | O(n) | O(1) | Best general solution. Simple to implement and optimal for most interview scenarios. |
| Sliding Window with Reversal Tracking | O(n) | O(n) | Useful when avoiding repeated flips or when modeling range operations efficiently. |
Frequently asked questions
Is Minimum Operations to Make Binary Array Elements Equal to One I easy or hard?
The problem is classified as Medium difficulty. The core idea is simple once you recognize the greedy rule that each index must be fixed immediately. The challenge comes from proving that earlier positions cannot be revisited and handling the boundary cases at the end of the array.
Minimum Operations to Make Binary Array Elements Equal to One I Python/Java solution
Python and Java implementations typically follow the greedy approach. Iterate through the array, flip the next three elements whenever a 0 is found, and count operations. Both languages achieve O(n) time complexity and constant extra space with straightforward loops and conditional checks.
How to solve Minimum Operations to Make Binary Array Elements Equal to One I in O(n)?
Iterate through the array from index 0 to n-3. Whenever you encounter a 0, flip the next three elements and increment the operation count. Continue until the scan finishes. If the final two elements still contain a 0, it is impossible to make the entire array equal to 1, so return -1.
What is the best approach for Minimum Operations to Make Binary Array Elements Equal to One I?
The greedy left-to-right flipping approach is the most efficient and widely used solution. When a 0 appears at index i, you flip the subarray [i, i+1, i+2] because it is the only operation that can fix that position. This guarantees each index is corrected exactly once. The algorithm runs in O(n) time with O(1) extra space.
Is Minimum Operations to Make Binary Array Elements Equal to One I asked at Google/Amazon/Meta?
Problems involving minimum flip operations and greedy bit manipulation frequently appear in interviews at companies like Amazon, Google, and Meta. Variants that involve flipping k consecutive bits or using prefix flip logic are common in coding interviews and competitive programming.
What data structure is used in Minimum Operations to Make Binary Array Elements Equal to One I?
The simplest solution uses only an array with in-place updates. An optimized variant uses a queue or prefix-style tracking structure to record when flip effects start and expire. These structures help simulate sliding window flips without modifying each element repeatedly.
What is the time complexity of Minimum Operations to Make Binary Array Elements Equal to One I?
The optimal solution runs in O(n) time because the array is scanned once from left to right. Each operation flips a constant-size window of three elements. Space complexity is O(1) for the greedy implementation or O(n) if using sliding window tracking structures.