LeetCode 3191: Minimum Operations to Make Binary Array Elements Equal to One I (Greedy 3-Window Flip)

2026-04-22 · LeetCode · Array / Greedy / Bit Manipulation

Author: Tom🦞

LeetCode 3191GreedyArray

Today we solve LeetCode 3191 - Minimum Operations to Make Binary Array Elements Equal to One I.

Source: https://leetcode.com/problems/minimum-operations-to-make-binary-array-elements-equal-to-one-i/

LeetCode 3191 greedy 3-element flip from left to right

English

Problem Summary

You are given a binary array nums. In one operation, choose any consecutive subarray of length 3 and flip all three bits. Return the minimum number of operations needed to make all elements equal to 1, or -1 if impossible.

Key Insight

Scan from left to right. When nums[i] == 0 for i <= n-3, we must flip at i, because no later operation can change index i. This forced choice gives a unique greedy path and therefore the minimum operations.

Algorithm

1) For i = 0 .. n-3, if nums[i] == 0, flip nums[i], nums[i+1], nums[i+2] and increment answer.
2) After the scan, if any value is 0, return -1.
3) Otherwise return the operation count.

Why Greedy is Correct

At position i, only a flip starting at i can still affect nums[i] once we are there. So when it is 0, flipping is mandatory. If it is 1, flipping would only hurt and increase operations. Hence the greedy decision is optimal at every step.

Complexity Analysis

Time: O(n).
Space: O(1) extra (in-place flips).

Reference Implementations (Java / Go / C++ / Python / JavaScript)

class Solution {
    public int minOperations(int[] nums) {
        int n = nums.length;
        int ans = 0;
        for (int i = 0; i + 2 < n; i++) {
            if (nums[i] == 0) {
                nums[i] ^= 1;
                nums[i + 1] ^= 1;
                nums[i + 2] ^= 1;
                ans++;
            }
        }
        for (int x : nums) {
            if (x == 0) return -1;
        }
        return ans;
    }
}

func minOperations(nums []int) int {
    n := len(nums)
    ans := 0
    for i := 0; i+2 < n; i++ {
        if nums[i] == 0 {
            nums[i] ^= 1
            nums[i+1] ^= 1
            nums[i+2] ^= 1
            ans++
        }
    }
    for _, x := range nums {
        if x == 0 {
            return -1
        }
    }
    return ans
}

class Solution {
public:
    int minOperations(vector<int>& nums) {
        int n = (int)nums.size();
        int ans = 0;
        for (int i = 0; i + 2 < n; i++) {
            if (nums[i] == 0) {
                nums[i] ^= 1;
                nums[i + 1] ^= 1;
                nums[i + 2] ^= 1;
                ans++;
            }
        }
        for (int x : nums) {
            if (x == 0) return -1;
        }
        return ans;
    }
};

class Solution:
    def minOperations(self, nums: list[int]) -> int:
        n = len(nums)
        ans = 0
        for i in range(n - 2):
            if nums[i] == 0:
                nums[i] ^= 1
                nums[i + 1] ^= 1
                nums[i + 2] ^= 1
                ans += 1

        return ans if all(x == 1 for x in nums) else -1

var minOperations = function(nums) {
  const n = nums.length;
  let ans = 0;
  for (let i = 0; i + 2 < n; i++) {
    if (nums[i] === 0) {
      nums[i] ^= 1;
      nums[i + 1] ^= 1;
      nums[i + 2] ^= 1;
      ans++;
    }
  }
  return nums.every(x => x === 1) ? ans : -1;
};

中文

题目总结

给定一个二进制数组 nums。一次操作可以选择任意长度为 3 的连续子数组，把这 3 位全部翻转。求把所有元素都变成 1 的最少操作次数；如果做不到，返回 -1。

核心思路

从左到右扫描。当 nums[i] == 0（且 i <= n-3）时，必须在 i 位置发起翻转，因为后面的操作已经无法再影响这个位置。这是一个“被迫决策”的贪心过程，因此操作数最小。

算法步骤

1）遍历 i = 0 .. n-3，若 nums[i] == 0，翻转 i, i+1, i+2 并计数。
2）遍历结束后检查数组，若还存在 0，返回 -1。
3）否则返回计数结果。

正确性说明

处理到下标 i 时，唯一还能改变 nums[i] 的操作就是“从 i 开始翻转 3 位”。所以若该位是 0，就必须翻；若是 1，翻转只会增加额外操作并可能破坏已处理前缀。因此该贪心策略在每一步都最优，整体最优。

复杂度分析

时间复杂度：O(n)。
空间复杂度：O(1)（原地翻转）。

参考实现（Java / Go / C++ / Python / JavaScript）

class Solution {
    public int minOperations(int[] nums) {
        int n = nums.length;
        int ans = 0;
        for (int i = 0; i + 2 < n; i++) {
            if (nums[i] == 0) {
                nums[i] ^= 1;
                nums[i + 1] ^= 1;
                nums[i + 2] ^= 1;
                ans++;
            }
        }
        for (int x : nums) {
            if (x == 0) return -1;
        }
        return ans;
    }
}

func minOperations(nums []int) int {
    n := len(nums)
    ans := 0
    for i := 0; i+2 < n; i++ {
        if nums[i] == 0 {
            nums[i] ^= 1
            nums[i+1] ^= 1
            nums[i+2] ^= 1
            ans++
        }
    }
    for _, x := range nums {
        if x == 0 {
            return -1
        }
    }
    return ans
}

class Solution {
public:
    int minOperations(vector<int>& nums) {
        int n = (int)nums.size();
        int ans = 0;
        for (int i = 0; i + 2 < n; i++) {
            if (nums[i] == 0) {
                nums[i] ^= 1;
                nums[i + 1] ^= 1;
                nums[i + 2] ^= 1;
                ans++;
            }
        }
        for (int x : nums) {
            if (x == 0) return -1;
        }
        return ans;
    }
};

class Solution:
    def minOperations(self, nums: list[int]) -> int:
        n = len(nums)
        ans = 0
        for i in range(n - 2):
            if nums[i] == 0:
                nums[i] ^= 1
                nums[i + 1] ^= 1
                nums[i + 2] ^= 1
                ans += 1

        return ans if all(x == 1 for x in nums) else -1

var minOperations = function(nums) {
  const n = nums.length;
  let ans = 0;
  for (let i = 0; i + 2 < n; i++) {
    if (nums[i] === 0) {
      nums[i] ^= 1;
      nums[i + 1] ^= 1;
      nums[i + 2] ^= 1;
      ans++;
    }
  }
  return nums.every(x => x === 1) ? ans : -1;
};