Max Consecutive Ones III [Medium] — Sliding Window with K Zeros

Problem Statement

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

Input: nums=[1,1,1,0,0,0,1,1,1,1,0], k=2 → Output: 6

Intuition

Sliding window counting zeros. Expand right, shrink left when zero count > k. Window size at any valid point = answer candidate.

Solutions

C++

int longestOnes(vector<int>& nums, int k) {
    int left=0, zeros=0, ans=0;
    for (int right=0;right<nums.size();right++) {
        if(!nums[right]) zeros++;
        while(zeros>k) { if(!nums[left]) zeros--; left++; }
        ans=max(ans,right-left+1);
    }
    return ans;
}

Java

public int longestOnes(int[] nums, int k) {
    int left=0, zeros=0, ans=0;
    for (int right=0;right<nums.length;right++) {
        if(nums[right]==0) zeros++;
        while(zeros>k){if(nums[left++]==0)zeros--;}
        ans=Math.max(ans,right-left+1);
    }
    return ans;
}

JavaScript

var longestOnes = function(nums, k) {
    let left=0, zeros=0, ans=0;
    for(let right=0;right<nums.length;right++){
        if(!nums[right]) zeros++;
        while(zeros>k){if(!nums[left++])zeros--;}
        ans=Math.max(ans,right-left+1);
    }
    return ans;
};

Python

def longestOnes(nums: list[int], k: int) -> int:
    left = zeros = ans = 0
    for right, val in enumerate(nums):
        if val == 0: zeros += 1
        while zeros > k:
            if nums[left] == 0: zeros -= 1
            left += 1
        ans = max(ans, right - left + 1)
    return ans

Complexity

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