⚡Flashcard Drill➔
NeetCode #769LC-3191MediumGreedy
← Back to All Problems

#769 · #3191 · Minimum Operations to Make Binary Array Elements Equal to One I(使二进制数组全部等于 1 的最少操作次数 I)

📌 Problem Statement & Constraints

Given a binary array nums, an operation chooses an index i <= n - 3 and flips nums[i], nums[i+1] and nums[i+2]. Return the minimum operations to make all elements 1, or -1 if impossible. Constraints: 3 <= nums.length <= 10^5, nums[i] is 0 or 1.

💡 Core Algorithmic Approaches

  1. Scan from left to right; once the scan passes index i, no operation can change it again.
  2. Therefore if nums[i] == 0, the only way to fix it is to flip the window starting at i.
  3. This makes the greedy forced: every zero encountered triggers exactly one operation.
  4. After the scan, only the last two elements are unconstrained; if either is 0, the array cannot be fixed.

💻 Benchmark Python3 Implementation

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

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(n): a single pass with O(1) work per index.
💾 Space Complexity
O(1) beyond the input (the array is modified in place).

⚠️ Interview Pitfalls & Follow-ups

  • Iterating to n instead of n - 2: an operation starting at n-2 would read out of bounds.
  • Skipping the final check: the last two elements may still be 0, in which case the answer is -1.
  • Flipping when nums[i] == 1: the greedy only acts on a zero.
  • Trying to choose windows freely: the left-to-right forcing argument shows the greedy is the only viable strategy.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🎯 Drill This Card Now➔

🧩 Related Greedy Problems