Max Consecutive Ones III

Problem

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

Example 1:

Input: nums = [1,1,1,0,0,0,1,1,1,1,0], k = 2
Output: 6
Explanation: [1,1,1,0,0,1,1,1,1,1,1]
Bolded numbers were flipped from 0 to 1. The longest subarray is underlined.

Example 2:

Input: nums = [0,0,1,1,0,0,1,1,1,0,1,1,0,0,0,1,1,1,1], k = 3
Output: 10
Explanation: [0,0,1,1,1,1,1,1,1,1,1,1,0,0,0,1,1,1,1]
Bolded numbers were flipped from 0 to 1. The longest subarray is underlined.

Constraints:

• 1 <= nums.length <= 10<sup>5</sup>
• nums[i] is either 0 or 1.
• 0 <= k <= nums.length

Solution

Brute force approach

Instead of flipping zeros, find the longest subarray containing at most k zeros. Those zeros can all be flipped to ones. This is the longest-window idea from pattern 2.

Try every starting index and extend the subarray to the right. Stop when the zero count exceeds k, because extending further cannot reduce it.

class Solution {
    public int longestOnes(int[] nums, int k) {
        int maxLength = 0;
        int n = nums.length;
        
        for(int i=0; i<n; i++){
            int zeros = 0;
            for(int j=i; j<n; j++){
                
                if(nums[j] == 0){
                    zeros += 1;
                }

                if(zeros > k){
                    break;
                }

                maxLength = Math.max(maxLength, j-i+1);
            }
        }

        return maxLength;
    }
}

Time: O(n²) in the worst case. Extra space: O(1).

Better solution

Use a window from l to r and track its zero count:

1. Add nums[r] to the window.
2. While there are more than k zeros, remove elements from the left.
3. Once valid, update the maximum length using r - l + 1.

class Solution {
    public int longestOnes(int[] nums, int k) {
        int maxLength = 0;
        int n = nums.length;
        
        int l = 0;
        int r = 0;
        int zeros = 0;

        while(r<n){
            if(nums[r] == 0) {
                zeros += 1;
            }

            while(zeros > k){
                if(nums[l] == 0){
                    zeros -= 1;
                }
                l += 1;
            }

            maxLength = Math.max(maxLength, r-l+1);

            r+=1;
        }

        return maxLength;
    }
}

Time: O(2n) — each pointer moves forward at most n times, even with the inner while loop. Extra space: O(1).

Optimal Solution

This version moves l only once per iteration when the zero count exceeds k. The window may still be invalid, so update the answer only when zeros <= k.

Each iteration adds one element and removes at most one, so the window length never decreases. This lets us keep searching for a longer valid window without fully shrinking each time.

class Solution {
    public int longestOnes(int[] nums, int k) {
        int maxLength = 0;
        int n = nums.length;
        
        int l = 0;
        int r = 0;
        int zeros = 0;

        while(r<n){
            if(nums[r] == 0) {
                zeros += 1;
            }

            if(zeros > k){
                if(nums[l] == 0){
                    zeros -= 1;
                }
                l += 1;
            }

            if(zeros <= k)
                maxLength = Math.max(maxLength, r-l+1);

            r+=1;
        }

        return maxLength;
    }
}

Time: O(n). Extra space: O(1). Both sliding-window versions have the same time complexity.