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] <= 1The 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.
C++
Java
Python
C#
JavaScript
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.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n).
Space Complexity: O(1).
| 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). |
Minimum Operations to Make Array Equal | Leetcode - 1551 • Algorithms Made Easy • 24,165 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