Problem 42.1 · Pattern Recognition DrillsMedium

Max Consecutive Ones III

What it teaches:

Practise it on judges as “Max Consecutive Ones III”.

In plain words

A row of light bulbs is a mix of on (1) and off (0), and you may switch on at most k of the off ones. Which stretch of bulbs can you make all lit? Keep a stretch that holds at most k off bulbs. Grow it to the right one bulb at a time; whenever it holds too many off bulbs, drop bulbs from its left end until it is fine again. The longest stretch you ever hold is the answer.

Return the length of the longest run of 1s after flipping at most k zeros. Example: nums = [1,1,1,0,0,0,1,1,1,1,0], k = 2 → 6.

The problem

Given a binary array and k, return the length of the longest run of 1s you can get by flipping at most k zeros.

Example 1

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

Constraints

1 ≤ n ≤ 10⁵

Pattern clues in the wording

→ Longest contiguous subarray
→ At most k exceptions inside

Stuck? Take one hint at a time

Solution · starter

class Solution {
    public int longestOnes(int[] nums, int k) {
        return 0;
    }
}

Write your solution locally or in your editor for now. Pick Java, Python, C++, JavaScript or Go above: every solution on this page switches with it. The in-browser runner will run these tests right here.

Test cases

#	Input	Expected
1	nums = [1,1,1,0,0,0,1,1,1,1,0] k = 2	6
2	nums = [0,0,1,1,0,0,1,1,1,0,1,1,0,0,0,1,1,1,1] k = 3	10

+ 1 hidden test the code runner will check

From slow to fast

Approaches

1. Variable window · O(n)

Variable window

Time O(n) Space O(1)

Count zeros in the window; shrink from the left while zeros > k; track the best length.

▶ Dry run: Grow right, shrink left when too many zerosnums = [1,1,1,0,0,0,1,1,1,1,0], k = 2

↑l

↑r

state(vars)

zeros: 2best: 5

Step 1/5Growing from the left, the window [0..4] holds two zeros, exactly k. Best so far: 5.

Approach 1

class Solution {
    public int longestOnes(int[] nums, int k) {
        int best = 0, zeros = 0;
        for (int l = 0, 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;
    }
}

Verdict: Each index enters and leaves once.

Before you submit

Edge cases and common mistakes

Test these inputs

k = 0
k ≥ number of zeros (whole array)

Mistakes people make

Trying every start position (O(n²)).

Interview

Follow-up questions

What if you could delete exactly one element instead?

Command Palette

The problem

Approaches

Variable window

Edge cases and common mistakes

Follow-up questions