Problem

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.

Examples

Example 1:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12


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:

1
2
3
4
5
6
7
8
9


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

Solution

Method 1 – Flip State Tracking (Greedy)

Intuition

The algorithm minimizes operations by toggling elements only when necessary, efficiently moving towards making all elements 1. By tracking the current flip state, we avoid redundant operations and only flip when the current value matches the flip state.

Approach

  1. Initialize a variable to track the number of flips and the current flip state.
  2. Iterate through the array from left to right.
  3. For each element, if its value equals the current flip state, increment the flip count and toggle the flip state.
  4. Continue until all elements are processed.
  5. Return the total number of flips.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

class Solution {
    public int minOperations(int[] nums) {
        int flips = 0;
        int flipped = 0;
        for (int num : nums) {
            if (num == flipped) {
                flips++;
                flipped ^= 1;
            }
        }
        return flips;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

class Solution {
public:
    int minOperations(vector<int>& nums) {
        int flips = 0, flipped = 0;
        for (int num : nums) {
            if (num == flipped) {
                flips++;
                flipped ^= 1;
            }
        }
        return flips;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10

func minOperations(nums []int) int {
    flips, flipped := 0, 0
    for _, num := range nums {
        if num == flipped {
            flips++
            flipped ^= 1
        }
    }
    return flips
}
1
2
3
4
5
6
7
8
9

class Solution:
    def minOperations(self, nums: list[int]) -> int:
        flips = 0
        flipped = 0
        for num in nums:
            if num == flipped:
                flips += 1
                flipped ^= 1
        return flips
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

impl Solution {
    pub fn min_operations(nums: Vec<i32>) -> i32 {
        let mut flips = 0;
        let mut flipped = 0;
        for num in nums {
            if num == flipped {
                flips += 1;
                flipped ^= 1;
            }
        }
        flips
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

class Solution {
    minOperations(nums: number[]): number {
        let flips = 0, flipped = 0;
        for (const num of nums) {
            if (num === flipped) {
                flips++;
                flipped ^= 1;
            }
        }
        return flips;
    }
}

Complexity

  • ⏰ Time complexity: O(n), since each element is processed once.
  • 🧺 Space complexity: O(1), only a few variables are used.