You are given a binary array nums.
You can do the following operation on the array any number of times (possibly zero):
i from the array and flip all the elements from index i to 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:
i = 1. The resulting array will be nums = [0,0,0,1,0].i = 0. The resulting array will be nums = [1,1,1,0,1].i = 4. The resulting array will be nums = [1,1,1,0,0].i = 3. The resulting array will be nums = [1,1,1,1,1].Example 2:
Input: nums = [1,0,0,0]
Output: 1
Explanation:
We can do the following operation:
i = 1. The resulting array will be nums = [1,1,1,1].
Constraints:
1 <= nums.length <= 1050 <= nums[i] <= 1Problem 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.
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.
The function iterates over each element of the array. When it encounters a '0', it increments the flip count and continues iterating over subsequent '0's to the next '1' or end of the array. This effectively counts distinct contiguous segments of '0's.
Time Complexity: O(n), where n is the number of elements in the array, as each element is processed at most twice.
Space Complexity: O(1), as no additional space is used apart from the input and a few variables.
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.
The key part of this C solution is the toggle, which helps track when an operation should occur based on the potential flip state of the array.
Time Complexity: O(n), where n is the length of the input array.
Space Complexity: O(1).
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).
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Approach 1: Linear Scan with Flip Counting | Time Complexity: O(n), where n is the number of elements in the array, as each element is processed at most twice. |
| Approach 2: Using a Toggle State | Time Complexity: O(n), where n is the length of the input array. |
| Bit Manipulation | — |
| 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. |
3192. Minimum Operations to Make Binary Array Elements Equal to One II (Leetcode Medium) • Programming Live with Larry • 514 views views
Watch 3 more video solutions →Practice Minimum Operations to Make Binary Array Elements Equal to One II with our built-in code editor and test cases.
Practice on FleetCode