Skip to main content
Talentd

Minimum Operations to Make Binary Array Elements Equal to One II - Solution & Explanation

MediumArrayDynamic ProgrammingGreedy15 min readAsked at: Uber
Practice this problem

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 index i from the array and flip all the elements from index i to the end of the array.

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.

 

Example 1:

Input: nums = [0,1,1,0,1]

Output: 4

Explanation:
We can do the following operations:

  • Choose the index i = 1. The resulting array will be nums = [0,0,0,1,0].
  • Choose the index i = 0. The resulting array will be nums = [1,1,1,0,1].
  • Choose the index i = 4. The resulting array will be nums = [1,1,1,0,0].
  • Choose the index i = 3. The resulting array will be nums = [1,1,1,1,1].

Example 2:

Input: nums = [1,0,0,0]

Output: 1

Explanation:
We can do the following operation:

  • Choose the index i = 1. The resulting array will be nums = [1,1,1,1].

 

Constraints:

  • 1 <= nums.length <= 105
  • 0 <= nums[i] <= 1

Approach Overview

Problem Overview: You are given a binary array and an operation that flips every element from index i to the end of the array. The goal is to compute the minimum number of such operations required so that every element becomes 1.

Approach 1: Linear Scan with Flip Counting (O(n) time, O(1) space)

Scan the array from left to right while tracking how many suffix flips have already been applied. Each flip inverts the meaning of future elements, so the effective value of nums[i] depends on whether the number of flips so far is even or odd. If the current effective value becomes 0, you must start a new flip operation at this index to turn it into 1. Increment the flip counter and continue scanning. This greedy decision works because once you pass an index, future operations cannot change it again without breaking previously fixed positions.

Approach 2: Using a Toggle State (O(n) time, O(1) space)

Instead of explicitly counting flips, maintain a boolean toggle state that represents whether the array is currently inverted due to previous operations. While iterating through the array, compute the effective bit by XORing the current value with the toggle state. If the effective bit is 0, perform an operation: increment the answer and flip the toggle state. This approach expresses the same greedy idea more cleanly by modeling the suffix flips as a state change. It avoids modifying the array and keeps the logic simple.

The key observation is that every index must become 1 before moving forward, because any operation later will flip the entire suffix and could undo your work. A single left‑to‑right pass is enough to determine when a flip must occur.

Recommended for interviews: The toggle‑state greedy scan is what interviewers expect. It shows you understand how suffix flips affect future elements and how to model the effect with a simple state variable. The solution runs in linear time with constant memory and uses concepts from Greedy decision making over an Array, sometimes framed with state transitions similar to Dynamic Programming.

Approach 1: Approach 1: Linear Scan with Flip Counting

This approach involves scanning through the array while counting the number of contiguous segments of '0's. Each segment can be flipped by choosing the first index of the segment, thus converting the whole segment into '1's. The aim is to count these segments and provide that as the result for minimum operations.

The function iterates over each element of the array. When it encounters a '0', it increments the flip count and continues iterating over subsequent '0's to the next '1' or end of the array. This effectively counts distinct contiguous segments of '0's.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n), where n is the number of elements in the array, as each element is processed at most twice.
Space Complexity: O(1), as no additional space is used apart from the input and a few variables.

Try this approach in the editor →

Approach 2: Approach 2: Using a Toggle State

This approach involves maintaining a toggle state that switches whenever a zero is encountered. By maintaining a toggle state, we can track the number of flip operations needed efficiently.

The key part of this C solution is the toggle, which helps track when an operation should occur based on the potential flip state of the array.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n), where n is the length of the input array.
Space Complexity: O(1).

Try this approach in the editor →

Approach 3: Bit Manipulation

We notice that whenever we change an element at a certain position to 1, all the elements to its right are flipped. Therefore, we can use a variable v to record whether the current position and all elements to its right have been flipped. If flipped, the value of v is 1, otherwise, it is 0.

We iterate through the array nums. For each element x, we perform an XOR operation between x and v. If x is 0, then we need to change x to 1, which requires a flip operation. We increment the answer by one and flip the value of v.

After the iteration, we can obtain the minimum number of operations.

The time complexity is O(n), where n is the length of the array nums. The space complexity is O(1).

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Approach 1: Linear Scan with Flip Counting

Time Complexity: O(n), where n is the number of elements in the array, as each element is processed at most twice.
Space Complexity: O(1), as no additional space is used apart from the input and a few variables.

Approach 2: Using a Toggle State

Time Complexity: O(n), where n is the length of the input array.
Space Complexity: O(1).

Bit Manipulation—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Linear Scan with Flip CountingO(n)O(1)General case. Tracks number of suffix flips and adjusts the effective bit during iteration.
Toggle State GreedyO(n)O(1)Cleanest implementation. Uses a boolean state to represent whether previous flips inverted the remaining suffix.

Video Solution

3192. Minimum Operations to Make Binary Array Elements Equal to One II (Leetcode Medium) • Programming Live with Larry • 520 views views

Watch 2 more video solutions →

Frequently Asked Questions

Is Minimum Operations to Make Binary Array Elements Equal to One II easy or hard?
The problem is typically rated Medium difficulty. The array traversal is straightforward, but recognizing that suffix flips can be represented using a toggle state is the key insight that makes the O(n) greedy solution possible.
Minimum Operations to Make Binary Array Elements Equal to One II Python/Java solution
Most implementations use a single loop with a flip parity variable. Python, Java, C++, and JavaScript solutions all follow the same pattern: iterate through the array, compute the effective bit using the flip state, and increment the operation count whenever the effective value is 0.
How to solve Minimum Operations to Make Binary Array Elements Equal to One II in O(n)?
Traverse the array while maintaining a flip parity or toggle state that represents whether the suffix has been inverted by previous operations. Compute the effective value of each element considering that state. If the effective value is 0, start a flip operation at that index and toggle the state. Continue until the end of the array.
What is the best approach for Minimum Operations to Make Binary Array Elements Equal to One II?
The optimal approach is a greedy linear scan with a toggle state. Iterate from left to right and track whether previous suffix flips inverted the current values. If the effective bit becomes 0, perform a flip and toggle the state. This solves the problem in O(n) time with O(1) extra space.
Is Minimum Operations to Make Binary Array Elements Equal to One II asked at Google/Amazon/Meta?
Greedy array‑transformation problems with suffix operations appear frequently in interviews at companies like Google, Amazon, and Meta. Variants that require tracking flip parity or lazy toggling are common because they test reasoning about state changes and optimal greedy decisions.
What data structure is used in Minimum Operations to Make Binary Array Elements Equal to One II?
The problem primarily uses a simple array traversal combined with a greedy state variable. No complex data structures are required. The solution maintains a flip counter or boolean toggle to represent the effect of previous suffix operations.
What is the time complexity of Minimum Operations to Make Binary Array Elements Equal to One II?
The optimal solution runs in O(n) time because the array is scanned once from left to right. Each index performs constant work to compute the effective bit and possibly toggle the flip state. The space complexity is O(1) since only a counter or boolean state is maintained.

Ready to solve this problem?

Practice Minimum Operations to Make Binary Array Elements Equal to One II with our built-in code editor and test cases.

Practice on FleetCode
Previous

Minimum Suffix Flips