Minimum Operations to Make Binary Array Elements Equal to One I
MedPrompt
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
Approaches
2 approaches with complexity analysis and trade-offs.
This approach uses a greedy strategy. We iterate through the array from left to right, deciding at each step whether a flip is necessary. To avoid modifying the original array, we use an auxiliary array to keep track of where flips have occurred. This allows us to calculate the true state of each element on the fly.
Algorithm
- Initialize
operations = 0, an integer arrayflipMarkersof sizento all zeros, andactiveFlips = 0. - Iterate through the array from
i = 0ton-1. - At each index
i, ifi >= 3, it means a flip that started ati-3has just ended its effect. We updateactiveFlipsby subtractingflipMarkers[i-3]. - Determine the current effective value of the element at
i. This is(nums[i] + activeFlips) % 2. TheactiveFlipsvariable tells us how many times the current element has been flipped by operations started ati-1andi-2. - If the effective value is
0, we must perform a flip.- First, check if a flip is possible. A flip must involve 3 consecutive elements, so we can only start a flip if
i <= n-3. Ifi > n-3and we need to flip, it's impossible, so return -1. - If possible, increment
operations, incrementactiveFlipsto account for the new flip, and markflipMarkers[i] = 1to record that a flip started ati.
- First, check if a flip is possible. A flip must involve 3 consecutive elements, so we can only start a flip if
- If the effective value is
1, the element is already correct, so we do nothing. - After the loop completes, return the total
operations.
Walkthrough
The core idea is to simulate the process without altering the input nums array. We maintain a running count of activeFlips that affect the current element nums[i]. An auxiliary array, flipMarkers, stores whether we decided to initiate a flip at any given index. When we are at index i, we first check if a flip that started at i-3 has now expired and adjust our activeFlips count accordingly. Then, we calculate the effective value of nums[i] by considering its original value and the activeFlips. If the effective value is 0, we are forced to perform a flip (if possible), incrementing our operation count and updating activeFlips and flipMarkers. If at any point we need to flip but cannot (i.e., we are too close to the end of the array), we conclude it's impossible.
public int minOperations(int[] nums) { int n = nums.length; int operations = 0; int[] flipMarkers = new int[n]; // 1 if a flip starts here, 0 otherwise int activeFlips = 0; for (int i = 0; i < n; i++) { if (i >= 3) { activeFlips -= flipMarkers[i - 3]; } int currentValue = (nums[i] + activeFlips) % 2; if (currentValue == 0) { if (i > n - 3) { return -1; // Cannot flip to make this element 1 } operations++; activeFlips++; flipMarkers[i] = 1; } } return operations;}Complexity
Time
O(N) - We iterate through the array once.
Space
O(N) - We use an auxiliary array `flipMarkers` of the same size as the input array.
Trade-offs
Pros
The logic is a clear simulation of the flip process.
It does not modify the original input array.
Cons
Requires O(N) extra space for the
flipMarkersarray, which is less efficient than constant space solutions.
This is the most efficient and straightforward approach. It relies on a greedy strategy where we iterate through the array and fix each element from left to right. By modifying the array in-place, we achieve an optimal solution with constant extra space.
Algorithm
- Initialize
operations = 0. - Iterate through the array with an index
ifrom0ton-3. - At each index
i, check the value ofnums[i]. Since we process from left to right, any operation starting beforeihas already been performed andnums[i]reflects its current state. - If
nums[i]is0, we must perform a flip operation starting ati. This is our only and last chance to makenums[i]a1. - To perform the flip, increment
operationsand toggle the values ofnums[i],nums[i+1], andnums[i+2]. (Note: flippingnums[i]is not strictly necessary as we won't visit it again, but it helps in visualizing the final state). - After the loop, the elements
nums[0]throughnums[n-3]are guaranteed to be1. - The last two elements,
nums[n-2]andnums[n-1], have had their final values determined by the preceding flips. We must check if they are both1. - If
nums[n-2] == 0ornums[n-1] == 0, it's impossible to make the array all ones, so return-1. - Otherwise, the array is all ones, and we return the total
operations.
Walkthrough
The key insight is that for any element nums[i], the decision to flip the triplet starting at i is determined solely by the current value of nums[i]. If we encounter a 0 at nums[i], we must flip the subarray [i, i+1, i+2]. If we don't, nums[i] will remain 0 because any future flips will start at an index greater than i and won't affect it. This greedy choice at each step ensures that we are always making a necessary move. We iterate up to the n-3-th element, making these forced moves. After this loop, the first n-2 elements are fixed to 1. The final state of the last two elements determines if a solution is possible. If they are also 1, we have found the minimum number of operations. If not, no solution exists.
public int minOperations(int[] nums) { int n = nums.length; int operations = 0; for (int i = 0; i <= n - 3; i++) { if (nums[i] == 0) { // We must perform a flip starting at i. operations++; // Flip the three consecutive elements. nums[i] = 1; nums[i + 1] = 1 - nums[i + 1]; nums[i + 2] = 1 - nums[i + 2]; } } // After the loop, check if the last two elements are 1. // nums[0...n-3] are guaranteed to be 1 by the loop logic. if (nums[n - 2] == 0 || nums[n - 1] == 0) { return -1; } return operations;}Complexity
Time
O(N) - We iterate through the array a single time.
Space
O(1) - We only use a few variables to store the count of operations and the loop index, modifying the array in-place.
Trade-offs
Pros
Extremely space-efficient, using only O(1) extra space.
The logic is simple and easy to implement.
Guaranteed to find the minimum number of operations if a solution exists.
Cons
This approach modifies the input array, which might not be permissible in some scenarios.
Solutions
Solution
class Solution {public int minOperations(int[] nums) { int ans = 0; int n = nums.length; for (int i = 0; i < n; ++i) { if (nums[i] == 0) { if (i + 2 >= n) { return -1; } nums[i + 1] ^= 1; nums[i + 2] ^= 1; ++ans; } } return ans; }}class Solution: def minOperations(self, nums: List[int]) -> int: ans = 0 for i, x in enumerate(nums): if x == 0: if i + 2 >= len(nums): return - 1 nums[i + 1] ^= 1 nums[i + 2] ^= 1 ans += 1 return ansclass Solution {public: int minOperations(vector<int> &nums) { int ans = 0; int n = nums.size(); for (int i = 0; i < n; ++i) { if (nums[i] == 0) { if (i + 2 >= n) { return -1; } nums[i + 1] ^= 1; nums[i + 2] ^= 1; ++ans; } } return ans; }};Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.