Minimum Operations to Make Binary Array Elements Equal to One II solution and explanation
2 more videos on this problem
3192. Minimum Operations to Make Binary Array Elements Equal to One II (Leetcode Medium)Programming Live with Larry · 9:00 · 520 views
3192. Minimum Operations to Make Binary Array Elements Equal to One IITech Courses · 9:23 · 386 views
LeetCode 3192 | Minimum Operations to Make Binary Array Elements Equal to One II | #leetcodecontestAlgo Horizon · 10:22 · 356 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 index
ifrom the array and flip all the elements from indexito the end of the array.
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.
Example 1:
Input: nums = [0,1,1,0,1]
Output: 4
Explanation:
We can do the following operations:
- Choose the index
i = 1. The resulting array will benums = [0,0,0,1,0]. - Choose the index
i = 0. The resulting array will benums = [1,1,1,0,1]. - Choose the index
i = 4. The resulting array will benums = [1,1,1,0,0]. - Choose the index
i = 3. The resulting array will benums = [1,1,1,1,1].
Example 2:
Input: nums = [1,0,0,0]
Output: 1
Explanation:
We can do the following operation:
- Choose the index
i = 1. The resulting array will benums = [1,1,1,1].
Constraints:
1 <= nums.length <= 1050 <= nums[i] <= 1
Approach overview
Problem Overview: You are given a binary array and an operation that flips every element from index i to the end of the array. The goal is to compute the minimum number of such operations required so that every element becomes 1.
Approach 1: Linear Scan with Flip Counting (O(n) time, O(1) space)
Scan the array from left to right while tracking how many suffix flips have already been applied. Each flip inverts the meaning of future elements, so the effective value of nums[i] depends on whether the number of flips so far is even or odd. If the current effective value becomes 0, you must start a new flip operation at this index to turn it into 1. Increment the flip counter and continue scanning. This greedy decision works because once you pass an index, future operations cannot change it again without breaking previously fixed positions.
Approach 2: Using a Toggle State (O(n) time, O(1) space)
Instead of explicitly counting flips, maintain a boolean toggle state that represents whether the array is currently inverted due to previous operations. While iterating through the array, compute the effective bit by XORing the current value with the toggle state. If the effective bit is 0, perform an operation: increment the answer and flip the toggle state. This approach expresses the same greedy idea more cleanly by modeling the suffix flips as a state change. It avoids modifying the array and keeps the logic simple.
The key observation is that every index must become 1 before moving forward, because any operation later will flip the entire suffix and could undo your work. A single left‑to‑right pass is enough to determine when a flip must occur.
Recommended for interviews: The toggle‑state greedy scan is what interviewers expect. It shows you understand how suffix flips affect future elements and how to model the effect with a simple state variable. The solution runs in linear time with constant memory and uses concepts from Greedy decision making over an Array, sometimes framed with state transitions similar to Dynamic Programming.
Approach 1: Approach 1: Linear Scan with Flip Counting
This approach involves scanning through the array while counting the number of contiguous segments of '0's. Each segment can be flipped by choosing the first index of the segment, thus converting the whole segment into '1's. The aim is to count these segments and provide that as the result for minimum operations.
def min_flips(nums):
flips = 0
i = 0
n = len(nums)
while i < n:
if nums[i] == 0:
flips += 1
while i < n and nums[i] == 0:
i += 1
else:
i += 1
return flips
print(min_flips([0, 1, 1, 0, 1]))public class Main {
public static int minFlips(int[] nums) {
int flips = 0;
int i = 0;
while (i < nums.length) {
if (nums[i] == 0) {
flips++;
while (i < nums.length && nums[i] == 0) {
i++;
}
} else {
i++;
}
}
return flips;
}
public static void main(String[] args) {
int[] nums = {0, 1, 1, 0, 1};
System.out.println(minFlips(nums));
}
}#include <iostream>
#include <vector>
using namespace std;
int minFlips(vector<int>& nums) {
int flips = 0;
int i = 0;
int n = nums.size();
while (i < n) {
if (nums[i] == 0) {
flips++;
while (i < n && nums[i] == 0) {
i++;
}
} else {
i++;
}
}
return flips;
}
int main() {
vector<int> nums = {0, 1, 1, 0, 1};
cout << minFlips(nums) << endl;
return 0;
}function minFlips(nums) {
let flips = 0;
let i = 0;
while (i < nums.length) {
if (nums[i] === 0) {
flips++;
while (i < nums.length && nums[i] === 0) {
i++;
}
} else {
i++;
}
}
return flips;
}
console.log(minFlips([0, 1, 1, 0, 1]));#include <stdio.h>
int minFlips(int* nums, int numsSize) {
int flips = 0;
int i = 0;
while (i < numsSize) {
if (nums[i] == 0) {
flips++;
while (i < numsSize && nums[i] == 0) {
i++;
}
} else {
i++;
}
}
return flips;
}
int main() {
int nums[] = {0, 1, 1, 0, 1};
int size = sizeof(nums) / sizeof(nums[0]);
printf("%d\n", minFlips(nums, size));
return 0;
}using System;
public class Solution {
public int MinFlips(int[] nums) {
int flips = 0;
int i = 0;
while (i < nums.Length) {
if (nums[i] == 0) {
flips++;
while (i < nums.Length && nums[i] == 0) {
i++;
}
} else {
i++;
}
}
return flips;
}
public static void Main() {
Solution sol = new Solution();
Console.WriteLine(sol.MinFlips(new int[] {0, 1, 1, 0, 1}));
}
}The Python function counts segments of zero using while loops. Every time it finds a new segment, it increments the flip counter by moving past contiguous '0's.
Time Complexity: O(n), where n is the length of the nums list.
Space Complexity: O(1).
Approach 2: Approach 2: Using a Toggle State
This approach involves maintaining a toggle state that switches whenever a zero is encountered. By maintaining a toggle state, we can track the number of flip operations needed efficiently.
def min_flips(nums):
flips = 0
toggle = 0
for num in nums:
if (num == 0 and toggle == 0) or (num == 1 and toggle == 1):
flips += 1
toggle = 1 - toggle
return flips
print(min_flips([0, 1, 1, 0, 1]))public class Main {
public static int minFlips(int[] nums) {
int flips = 0;
int toggle = 0;
for (int num : nums) {
if ((num == 0 && toggle == 0) || (num == 1 && toggle == 1)) {
flips++;
toggle = 1 - toggle;
}
}
return flips;
}
public static void main(String[] args) {
int[] nums = {0, 1, 1, 0, 1};
System.out.println(minFlips(nums));
}
}#include <iostream>
#include <vector>
using namespace std;
int minFlips(vector<int>& nums) {
int flips = 0;
int toggle = 0;
for (int num : nums) {
if ((num == 0 && toggle == 0) || (num == 1 && toggle == 1)) {
flips++;
toggle = 1 - toggle;
}
}
return flips;
}
int main() {
vector<int> nums = {0, 1, 1, 0, 1};
cout << minFlips(nums) << endl;
return 0;
}function minFlips(nums) {
let flips = 0;
let toggle = 0;
for (let num of nums) {
if ((num === 0 && toggle === 0) || (num === 1 && toggle === 1)) {
flips++;
toggle = 1 - toggle;
}
}
return flips;
}
console.log(minFlips([0, 1, 1, 0, 1]));#include <stdio.h>
int minFlips(int* nums, int numsSize) {
int flips = 0;
int toggle = 0;
for (int i = 0; i < numsSize; i++) {
if ((nums[i] == 0 && toggle == 0) || (nums[i] == 1 && toggle == 1)) {
flips++;
toggle = 1 - toggle;
}
}
return flips;
}
int main() {
int nums[] = {0, 1, 1, 0, 1};
int size = sizeof(nums) / sizeof(nums[0]);
printf("%d\n", minFlips(nums, size));
return 0;
}using System;
public class Solution {
public int MinFlips(int[] nums) {
int flips = 0;
int toggle = 0;
foreach (int num in nums) {
if ((num == 0 && toggle == 0) || (num == 1 && toggle == 1)) {
flips++;
toggle = 1 - toggle;
}
}
return flips;
}
public static void Main() {
Solution sol = new Solution();
Console.WriteLine(sol.MinFlips(new int[] {0, 1, 1, 0, 1}));
}
}This Python code uses a toggle state to switch when a mismatch occurs. It results in a more efficient counting of required flip operations.
Time Complexity: O(n), where n is the list's length.
Space Complexity: O(1).
Approach 3: Bit Manipulation
We notice that whenever we change an element at a certain position to 1, all the elements to its right are flipped. Therefore, we can use a variable v to record whether the current position and all elements to its right have been flipped. If flipped, the value of v is 1, otherwise, it is 0.
We iterate through the array nums. For each element x, we perform an XOR operation between x and v. If x is 0, then we need to change x to 1, which requires a flip operation. We increment the answer by one and flip the value of v.
After the iteration, we can obtain the minimum number of operations.
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 {
let [ans, v] = [0, 0];
for (let x of nums) {
x ^= v;
if (x === 0) {
v ^= 1;
++ans;
}
}
return ans;
}func minOperations(nums []int) (ans int) {
v := 0
for _, x := range nums {
x ^= v
if x == 0 {
v ^= 1
ans++
}
}
return
}Complexity comparison
| Approach | Complexity |
|---|---|
| Approach 1: Linear Scan with Flip Counting | Time Complexity: O(n), where n is the length of the nums list. |
| Approach 2: Using a Toggle State | Time Complexity: O(n), where n is the list's length. |
| Bit Manipulation | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Linear Scan with Flip Counting | O(n) | O(1) | General case. Tracks number of suffix flips and adjusts the effective bit during iteration. |
| Toggle State Greedy | O(n) | O(1) | Cleanest implementation. Uses a boolean state to represent whether previous flips inverted the remaining suffix. |
Frequently asked questions
Is Minimum Operations to Make Binary Array Elements Equal to One II easy or hard?
The problem is typically rated Medium difficulty. The array traversal is straightforward, but recognizing that suffix flips can be represented using a toggle state is the key insight that makes the O(n) greedy solution possible.
Minimum Operations to Make Binary Array Elements Equal to One II Python/Java solution
Most implementations use a single loop with a flip parity variable. Python, Java, C++, and JavaScript solutions all follow the same pattern: iterate through the array, compute the effective bit using the flip state, and increment the operation count whenever the effective value is 0.
How to solve Minimum Operations to Make Binary Array Elements Equal to One II in O(n)?
Traverse the array while maintaining a flip parity or toggle state that represents whether the suffix has been inverted by previous operations. Compute the effective value of each element considering that state. If the effective value is 0, start a flip operation at that index and toggle the state. Continue until the end of the array.
What is the best approach for Minimum Operations to Make Binary Array Elements Equal to One II?
The optimal approach is a greedy linear scan with a toggle state. Iterate from left to right and track whether previous suffix flips inverted the current values. If the effective bit becomes 0, perform a flip and toggle the state. This solves the problem in O(n) time with O(1) extra space.
Is Minimum Operations to Make Binary Array Elements Equal to One II asked at Google/Amazon/Meta?
Greedy array‑transformation problems with suffix operations appear frequently in interviews at companies like Google, Amazon, and Meta. Variants that require tracking flip parity or lazy toggling are common because they test reasoning about state changes and optimal greedy decisions.
What data structure is used in Minimum Operations to Make Binary Array Elements Equal to One II?
The problem primarily uses a simple array traversal combined with a greedy state variable. No complex data structures are required. The solution maintains a flip counter or boolean toggle to represent the effect of previous suffix operations.
What is the time complexity of Minimum Operations to Make Binary Array Elements Equal to One II?
The optimal solution runs in O(n) time because the array is scanned once from left to right. Each index performs constant work to compute the effective bit and possibly toggle the flip state. The space complexity is O(1) since only a counter or boolean state is maintained.