You are given a binary array nums.
You can do the following operation on the array any number of times (possibly zero):
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:
nums = [1,0,0,1,0,0].nums = [1,1,1,0,0,0].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] <= 1Problem 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.
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.
Implementation detail: We iterate through the array from left to right and whenever we encounter a 0 at index i, we flip 3 consecutive elements starting at i. If after processing the entire array the last elements still contain 0, it implies that it's impossible to fulfill the condition, thus return -1. Otherwise, return the number of flips performed.
Time Complexity: O(n), where n is the number of elements in the array. We go through the array linearly.
Space Complexity: O(1), as we do not use any additional data structures.
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.
Implementation detail: The algorithm uses a flip tracking variable need_flip, which represents if a virtual flip has been done to a section of the array without directly modifying it. It flips when the current need flip doesn't satisfy conditions, and adjusts when crossing the 3-length boundary.
Time Complexity: O(n).
Space Complexity: O(1).
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).
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Greedy Approach | Time Complexity: O(n), where n is the number of elements in the array. We go through the array linearly. |
| Sliding Window with Reversal Tracking | Time Complexity: O(n). |
| Sequential Traversal + Simulation | — |
| 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. |
Minimum Operations to Make Binary Array Elements Equal to One I - Leetcode 3191 - Python • NeetCodeIO • 9,452 views views
Watch 9 more video solutions →Practice Minimum Operations to Make Binary Array Elements Equal to One I with our built-in code editor and test cases.
Practice on FleetCode