⚡Flashcard Drill➔
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

  1. Maintain a window containing at most k zeros; its length is a candidate answer.
  2. Expand the right end; when the zero count exceeds k, shrink from the left until it is back within budget.
  3. Track the maximum window length.
  4. 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 >= k in the condition: up to k flips are allowed, so the window is invalid only when the count exceeds k.
  • Returning the number of ones: the window length includes the flipped zeros.
  • Using a while loop 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.
🎯 Drill This Card Now➔

🧩 Related Sliding Window Problems