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
- Scan from left to right; once the scan passes index
i, no operation can change it again. - Therefore if
nums[i] == 0, the only way to fix it is to flip the window starting ati. - This makes the greedy forced: every zero encountered triggers exactly one operation.
- 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
ninstead ofn - 2: an operation starting atn-2would 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.