Max Consecutive Ones III — Sliding Window with K Flips [Google, Meta Medium]

Problem Statement

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

Intuition: Sliding window: expand right always; when zeros in window > k, shrink from left. Track max window size.

C Solution
C++ Solution
Java Solution
JavaScript Solution
Python Solution
Complexity

C Solution

int longestOnes(int* n,int sz,int k){int l=0,z=0,best=0;for(int r=0;r<sz;r++){if(!n[r])z++;while(z>k){if(!n[l++])z--;}best=best>r-l+1?best:r-l+1;}return best;}

C++ Solution

class Solution {
public:
    int longestOnes(vector<int>& nums, int k) {
        int l = 0, zeros = 0, best = 0;
        for (int r = 0; r < (int)nums.size(); r++) {
            if (!nums[r]) zeros++;
            while (zeros > k) { if (!nums[l++]) zeros--; }
            best = max(best, r - l + 1);
        }
        return best;
    }
};

Java Solution

class Solution {
    public int longestOnes(int[] nums, int k) {
        int l = 0, zeros = 0, best = 0;
        for (int r = 0; r < nums.length; r++) {
            if (nums[r] == 0) zeros++;
            while (zeros > k) { if (nums[l++] == 0) zeros--; }
            best = Math.max(best, r - l + 1);
        }
        return best;
    }
}

JavaScript Solution

function longestOnes(nums, k) {
    let l = 0, zeros = 0, best = 0;
    for (let r = 0; r < nums.length; r++) {
        if (nums[r] === 0) zeros++;
        while (zeros > k) { if (nums[l++] === 0) zeros--; }
        best = Math.max(best, r - l + 1);
    }
    return best;
}

Python Solution

def longestOnes(nums, k):
    l = zeros = best = 0
    for r, n in enumerate(nums):
        if n == 0: zeros += 1
        while zeros > k:
            if nums[l] == 0: zeros -= 1
            l += 1
        best = max(best, r - l + 1)
    return best

Complexity

| O(n) time | O(1) space |