Max Consecutive Ones III

Interview Problem Intermediate Medium Variable-size Window Array

Checking your account…

Loading the interactive Interview workspace.If it does not appear, the problem and learning material remain readable, but browser execution is unavailable.Reload Interview workspace

Problem

Implement Solution.longestOnes(nums, k). nums is binary. Return the maximum length of a contiguous subarray that can become all ones after flipping at most k zeros.

Starter code

class Solution:
    def longestOnes(self, nums, k):
        pass

Test cases

two-flips

Expected: 6

Wizard outline

Step 1: Initialize Solution.longestOnes
Replace the empty starter with the first real state owned by Solution.longestOnes. A small, named state is easier to verify than a complete algorithm. Establish it before adding the branch or loop that changes it.
Step 2: Pass the Three Flips case
Complete the readable core algorithm for one representative Interview case. Maintain a variable-size window whose zero count never exceeds k.
Step 3: Harden the Two Flips boundary
Repair the reviewed boundary and pass the complete submission contract. After shrinking, the window contains at most k zeros and is feasible. Left advances only when necessary, so for each right endpoint this is the longest feasible ending window; the maximum over endpoints is optimal.

Footguns and prerequisites

Shrink in a while loop because a newly added zero may require removing several leading ones before the oldest zero leaves.
arrays strings two pointers sliding window

Reviewed references

LeetCode 1004 — Max Consecutive Ones III

Practice prerequisites

Shrink Until the Window Is Valid(opens in a new tab)
Shrink Until the Window Is Valid isolates after shrinking, the current half-open window is valid and no earlier left boundary works for the same right endpoint. That focused state discipline is required when implementing max consecutive ones three as a complete Interview Problem.

Recommended approach and implementation

Expand right and count zeros; while zeros exceed k, remove nums[left] from the count and advance left, then record the valid length.

Why it works: After shrinking, the window contains at most k zeros and is feasible. Left advances only when necessary, so for each right endpoint this is the longest feasible ending window; the maximum over endpoints is optimal.

class Solution:
    def longestOnes(self, nums, k):
        """
        Checkpoint 1: initialize the state owned by this Interview contract.
        Checkpoint 2: assemble the primary transition without hiding the boundary.
        """
        left = zeros = best = 0
        for right, value in enumerate(nums):
            if value == 0:
                zeros += 1
            while zeros > k:
                if nums[left] == 0:
                    zeros -= 1
                left += 1
            best = max(best, right - left + 1)
        return best

Similar exercises

Longest Repeating Character Replacement(opens in a new tab)