NeetCode #225LC-487MediumSliding WindowNC Algo100
← Back to All Problems#225 · #487 · Max Consecutive Ones II(最大连续 1 的个数 II)
📌 Problem Statement & Constraints
Given a binary array
nums, return the maximum number of consecutive 1s obtainable if you can flip at most one 0. Constraints: 1 <= nums.length <= 10^5.💡 Core Algorithmic Approaches
- This is Max Consecutive Ones III with
k = 1: a sliding window containing at most one zero. - Expand the right end; when the zero count exceeds one, shrink from the left.
- The window length is the candidate answer.
- An alternative is to track the lengths of runs of ones and combine adjacent runs separated by a single zero.
💻 Benchmark Python3 Implementation
class Solution:
def findMaxConsecutiveOnes(self, nums: List[int]) -> int:
l = 0
zeros = 0
best = 0
for r, x in enumerate(nums):
if x == 0:
zeros += 1
while zeros > 1: # more than one zero -> invalid
if nums[l] == 0:
zeros -= 1
l += 1
best = max(best, r - l + 1)
return best⚡ Complexity Deep Dive
⏱️ Time Complexity
O(n): each element enters and leaves the window at most once.
💾 Space Complexity
O(1): two scalars.
⚠️ Interview Pitfalls & Follow-ups
- Allowing two zeros: the limit is exactly one flip.
- Decrementing the zero count for every element leaving the window: only zeros should decrement it.
- Assuming the array contains a zero: an all-ones array works fine, since the window never needs to shrink.
- Returning the number of ones instead of the window length: the flipped zero also counts toward the length.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🧩 Related Sliding Window Problems
#219 · #219Contains Duplicate II#220 · #121Best Time to Buy and Sell Stock#221 · #2379Minimum Recolors to Get K Consecutive Black Blocks#222 · #1984Minimum Difference Between Highest and Lowest of K Scores#223 · #1343Number of Sub-arrays of Size K and Average Greater than or Equal to Threshold#224 · #1052Grumpy Bookstore Owner