Max Consecutive Ones III (At Most K Flips)

Problem

Find the length of the longest subarray of 1s obtainable after flipping at most k zeroes to ones.

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

Python Solution

def longest_ones(nums, k):
    left = 0
    zeros = 0
    best = 0
    for right, num in enumerate(nums):
        if num == 0:
            zeros += 1
        while zeros > k:
            if nums[left] == 0:
                zeros -= 1
            left += 1
        best = max(best, right - left + 1)
    return best

C++ Solution

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

Java Solution

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

Complexity

Time: O(n) — the left pointer only ever moves forward, so both pointers together cross the array once. Space: O(1) — only a zero counter and two pointers are kept. This generalises Max Consecutive Ones to allow k flips.