Max Consecutive Ones III | Leetcode 1004 | Fixed Window Solution

The problem “Max Consecutive Ones III” asks for the length of the longest subarray containing only 1s after flipping at most k zeros to 1s. This is a classic sliding window problem where we maintain a window with at most k zeros.

Here’s the [Problem Link] to begin with.

Given a binary array nums and an integer k, return the maximum number of consecutive 1‘s in the array if you can flip at most k 0‘s.

Example 1:

Input: nums = [1,1,1,0,0,0,1,1,1,1,0], k = 2
Output: 6
Explanation: [1,1,1,0,0,1,1,1,1,1,1]
Bolded numbers were flipped from 0 to 1. The longest subarray is underlined.

Example 2:

Input: nums = [0,0,1,1,0,0,1,1,1,0,1,1,0,0,0,1,1,1,1], k = 3
Output: 10
Explanation: [0,0,1,1,1,1,1,1,1,1,1,1,0,0,0,1,1,1,1]
Bolded numbers were flipped from 0 to 1. The longest subarray is underlined.

Constraints:

• 1 <= nums.length <= 105
• nums[i] is either 0 or 1.
• 0 <= k <= nums.length

Brute Force (Check All Windows)

Intuition and Approach

• For each start index i, expand the end index j while counting zeros.
• If zeros exceed k, stop and move the start.
• Track the maximum length over all valid windows.
• Simple and clear, but O(n^2) time.

Code

class Solution:
    def longestOnes(self, nums: List[int], k: int) -> int:
        max_length = 0
        n = len(nums)
        for i in range(n):
            zeros = 0
            for j in range(i, n):
                if nums[j] == 0:
                    zeros += 1
                if zeros <= k:
                    length = j - i + 1
                    max_length = max(max_length, length)
                else:
                    break
        return max_length

Time and Space Complexity

• Time: O(n^2)
• Space: O(1)

When to use

• Good for understanding; not suitable for large inputs.

Better (Sliding Window with Shrink Loop)

Intuition and Approach

• Use two pointers (left, right) to maintain a window.
• Expand right; when zeros exceed k, shrink from left until zeros ≤ k again.
• Update the max length whenever the window is valid.

Code

class Solution:
    def longestOnes(self, nums: List[int], k: int) -> int:
        max_length = 0
        left = 0
        right = 0
        zeros = 0
        n = len(nums)
        while right < n:
            if nums[right] == 0:
                zeros += 1
            while zeros > k:
                if nums[left] == 0:
                    zeros -= 1
                left += 1
            if zeros <= k:
                length = right - left + 1
                max_length = max(max_length, length)
            right += 1
        return max_length

Time and Space Complexity

• Time: O(n)
• Space: O(1)

Why it works

• Maintains a window that always has at most k zeros by shrinking intelligently.

Optimal (Tight Sliding Window)

Intuition and Approach

• Same idea as “Better,” but with a slightly tighter structure:
  • Expand right, increment zeros on zero.
  • If zeros exceed k, move left by one (and decrement zero count if needed).
  • Update max length whenever the window is valid.

Code

class Solution:
    def longestOnes(self, nums: List[int], k: int) -> int:
        left = 0
        right = 0
        n = len(nums)
        zeros = 0
        max_length = 0
        while right < n:
            if nums[right] == 0:
                zeros += 1
            if zeros > k:
                if nums[left] == 0:
                    zeros -= 1
                left += 1
            if zeros <= k:
                length = right - left + 1
                max_length = max(max_length, length)
            right += 1
        return max_length

Time and Space Complexity

• Time: O(n)
• Space: O(1)

Why this is optimal

• Each index is visited at most twice (once by right, once by left), ensuring linear time with constant extra space.

Common Pitfalls and Tips

• Always ensure the window has at most k zeros by adjusting left when needed.
• The window length is always right - left + 1 after adjustments.
• Works for any k ≥ 0, including k = 0 (pure longest consecutive ones).

Final Takeaway

• Use Brute Force for learning.
• Prefer the Sliding Window solutions (Better and Optimal) for O(n) performance.
• The pattern, keep a window with a bounded count (here, zeros ≤ k), is a foundational sliding window technique used across many array and string problems.

For any changes to the article, kindly email at code@codeanddebug.in or contact us at +91-9712928220.