Minimum Operations to Make Binary Array Elements Equal to One I - Solution & Explanation
Problem Statement
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.
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.
Complexity
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.
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.
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.
Complexity
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).
Code
Python
Java
C++
Go
TypeScript
Complexity Comparison
| 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 | — |
Detailed 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. |
Video Solution
Minimum Operations to Make Binary Array Elements Equal to One I - Leetcode 3191 - Python • NeetCodeIO • 9,725 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Minimum Operations to Make Binary Array Elements Equal to One I easy or hard?
Minimum Operations to Make Binary Array Elements Equal to One I Python/Java solution
How to solve Minimum Operations to Make Binary Array Elements Equal to One I in O(n)?
What is the best approach for Minimum Operations to Make Binary Array Elements Equal to One I?
Is Minimum Operations to Make Binary Array Elements Equal to One I asked at Google/Amazon/Meta?
What data structure is used in Minimum Operations to Make Binary Array Elements Equal to One I?
What is the time complexity of Minimum Operations to Make Binary Array Elements Equal to One I?
Ready to solve this problem?
Practice Minimum Operations to Make Binary Array Elements Equal to One I with our built-in code editor and test cases.
Practice on FleetCode