Mastering the Max Consecutive Ones III Problem in Python – LeetCode 75 Explained

The Max Consecutive Ones III problem from LeetCode 75 is a classic interview question that tests your mastery of the sliding window technique. This problem focuses on array traversal, window adjustment and constraint handling. The challenge: given a binary array nums and an integer k, find the maximum number of consecutive 1s in the array if you can flip at most k zeros.

In this blog, we’ll break down the problem, explain it with examples, and walk through a clean Python solution step by step.

Problem Statement

You are given a binary array nums and an integer k. You can flip at most k zeros to ones. Return the maximum number of consecutive 1s in the array after flipping at most k zeros.

Understanding the Problem

The problem asks us to find the longest subarray of 1s after we are allowed to flip at most k zeros.

A subarray is a contiguous sequence in the array.
Flipping means converting a 0 to a 1.

Naively checking all subarrays would take too long. Instead, the sliding window technique allows us to solve this in linear time.

Examples

Example 1

Input: nums = [1,1,1,0,0,0,1,1,1,1,0], k = 2
Output: 6
Explanation: By flipping the zeros at indices 3 and 4, the longest subarray of 1s is [1,1,1,1,1,1].

Example 2

Input: nums = [0,0,1,1,1,0,0], k = 3
Output: 7
Explanation: Flip all three zeros → entire array becomes consecutive ones.

Python Solution – Step-by-Step Explanation

from typing import List

class Solution:
    def longestOnes(self, nums: List[int], k: int) -> int:
        left = 0
        max_length = 0

        for right in range(len(nums)):
            if nums[right] == 0:
                k -= 1  # Use one flip

                # Shrink the window until flips used ≤ k
                while k < 0:
                    if nums[left] == 0:
                        k += 1  # Restore a flip
                    left += 1

            # Update maximum length of valid window
            max_length = max(max_length, right - left + 1)

        return max_length

Step 1: Initialize pointers and variables

left = 0
max_length = 0

left marks the start of the window.
max_length tracks the best result.

Step 2: Expand the window with the right pointer

for right in range(len(nums)):
    if nums[right] == 0:
        k -= 1

Move right through the array.
If we encounter a zero, we use one flip (k -= 1).

Step 3: Shrink the window when flips exceed k

while k < 0:
    if nums[left] == 0:
        k += 1
    left += 1

If flips exceed allowed k, shrink from the left until the window is valid again.
Moving past a zero restores one flip.

Step 4: Update the maximum length

max_length = max(max_length, right - left + 1)

Track the longest valid subarray seen so far.

Why This Solution Works

Sliding window ensures we examine each element only once.
Instead of recalculating subarray sums, we only adjust the window edges.
Works for both small and large arrays efficiently.

Time and Space Complexity

Metric	Value
Time Complexity	O(n) – each index visited at most twice
Space Complexity	O(1) – only pointers and counters used

Edge Cases to Consider

Input	k	Output	Explanation
[1,1,1], 1	1	3	No flips needed
[0,0,0], 2	2	2	Flip any two zeros
[1,0,1,0,1], 1	1	3	Flip one zero to connect sequences
[1], 0	0	1	Single element, no flips allowed

Real-World Applications

Network reliability: Maximum consecutive successful signals with limited retries.
Quality control: Maximum consecutive defect-free products allowing limited corrections.
Stock analysis: Longest streak of profitable days after adjusting a few bad days.

Conclusion

The Max Consecutive Ones III problem is an excellent example of the sliding window technique. By adjusting window edges dynamically, we achieve an efficient O(n) solution that handles real-world constraints elegantly.

Mastering this problem will not only help in coding interviews but also in understanding streaming and window-based computations in data systems.

References

LeetCode Problem 1004: Max Consecutive Ones III

Sliding Window Technique