Watch 10 video solutions for Minimum Operations to Make Binary Array Elements Equal to One I, a medium level problem involving Array, Bit Manipulation, Queue. This walkthrough by NeetCodeIO has 9,452 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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. |