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.
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; }}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.