NeetCode #246LC-1004MediumSliding Window
← Back to All Problems#246 · #1004 · Max Consecutive Ones III(最大连续 1 的个数 III)
📌 Problem Statement & Constraints
Given a binary array
nums and an integer k, return the maximum number of consecutive 1s obtainable if you can flip at most k zeros. Constraints: 1 <= nums.length <= 10^5, nums[i] is 0 or 1, 0 <= k <= nums.length.💡 Core Algorithmic Approaches
- Maintain a window containing at most
kzeros; its length is a candidate answer. - Expand the right end; when the zero count exceeds
k, shrink from the left until it is back within budget. - Track the maximum window length.
- This is the template for the whole family of "at most k violations" window problems.
💻 Benchmark Python3 Implementation
class Solution:
def longestOnes(self, nums: List[int], k: int) -> int:
l = 0
zeros = 0
best = 0
for r, x in enumerate(nums):
if x == 0:
zeros += 1
while zeros > k: # over budget -> shrink
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
- Decrementing the zero count for every element leaving the window: only zeros should decrement it.
- Using
>= kin the condition: up tokflips are allowed, so the window is invalid only when the count exceedsk. - Returning the number of ones: the window length includes the flipped zeros.
- Using a
whileloop that shrinks by more than one: shrinking one element at a time is required to find the maximal window.
⚡
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