Topics › Sliding Window and Two Pointers › Medium Problems

Max Consecutive Ones III

Medium TUF ID 930 A2Z

LeetCode ↗ Java source ↗ Edit this article ↗

Jump to code: Brute Better Optimal

Problem

You are given a binary array nums (every element is 0 or 1) and an integer k. You may flip at most k zeros into ones. Return the length of the longest block of consecutive ones you can obtain.

Flipping is only a way of phrasing the question. The real question is: what is the longest subarray that contains at most k zeros? Any such subarray can be turned into all ones by flipping its zeros, and any all-ones block after flipping came from a subarray with at most k zeros.

Constraints: 1 ≤ n ≤ 10^5, 0 ≤ k ≤ n.

Example 1

nums = [1,1,1,0,0,0,1,1,1,1,0], k = 2
answer = 6          // nums[4..9] = [0,0,1,1,1,1] has two zeros; flip both to get six ones

Example 2

nums = [1,0,1,1], k = 0
answer = 2          // no flips allowed, so this is just the longest run of ones

Approach 1: Brute force

Intuition. Try every subarray and keep those with at most k zeros. Fix the start i, extend j, and count zeros as you go. Once the count exceeds k, every longer subarray from the same start also has more than k zeros, so we can stop extending.

Algorithm.

1. For each start i, set zeros = 0.
2. For j = i ..: if nums[j] == 0, increment zeros. If zeros > k, break. Otherwise update best with j - i + 1.
3. Return best.

static int bruteForce(int[] nums, int k) {
    int n = nums.length, best = 0;
    for (int i = 0; i < n; i++) {
        int zeros = 0;
        for (int j = i; j < n; j++) {
            if (nums[j] == 0) zeros++;
            if (zeros > k) break;                  // any longer window from i also has too many zeros
            best = Math.max(best, j - i + 1);
        }
    }
    return best;
}

Complexity. Time O(n^2): for an array of all ones the inner loop never breaks early. Space O(1).

Approach 2: Better, shrinking sliding window

Intuition. The property “has at most k zeros” is monotonic: if a window is valid, every window inside it is valid; if it is invalid, every window containing it is invalid. That is exactly the condition under which a two-pointer window works. Grow the right edge r one step at a time. Whenever the window picks up its (k+1)-th zero, advance the left edge l until one zero has left the window. At that point nums[l..r] is the longest valid window that ends at r, so we compare its length with the best.

Why is it the longest one ending at r? Because l is only advanced when the window is invalid, and an invalid window cannot become valid by moving l back to the left.

Algorithm.

1. l = 0, zeros = 0, best = 0.
2. For each r: if nums[r] == 0, increment zeros.
3. While zeros > k: if nums[l] == 0, decrement zeros; increment l.
4. Update best with r - l + 1.

static int better(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--;
            l++;
        }
        best = Math.max(best, r - l + 1);
    }
    return best;
}

Complexity. Time O(2n): r visits each index once and l visits each index at most once over the whole run. Space O(1).

Approach 3: Optimal, the window that never shrinks

Intuition. We only care about the maximum length. Once we have seen a valid window of length L, a window shorter than L can never improve the answer. So when the window becomes invalid, instead of shrinking it until it is valid, we slide it: move l forward by exactly one step, the same amount r just moved. The window keeps its length L. It may stay invalid for a while, and that is fine; we just do not record anything while it is invalid. When a longer valid window exists, r will reach its end with the window valid and of length L + 1, and the answer grows.

This removes the inner while loop. The asymptotic bound is the same O(n) as Approach 2, but the code does at most one left-step per right-step, which is the tightest form of the pattern and appears in many sliding-window problems.

Algorithm.

1. l = 0, zeros = 0, best = 0.
2. For each r: add nums[r] to the zero count.
3. If zeros > k: remove nums[l] from the count and increment l (one step only).
4. If zeros <= k, update best with r - l + 1.

static int optimal(int[] nums, int k) {
    int l = 0, zeros = 0, best = 0;
    for (int r = 0; r < nums.length; r++) {
        if (nums[r] == 0) zeros++;
        if (zeros > k) {                           // slide instead of shrink: length stays at the best so far
            if (nums[l] == 0) zeros--;
            l++;
        }
        if (zeros <= k) best = Math.max(best, r - l + 1);
    }
    return best;
}

Dry run on nums = [1,1,1,0,0,0,1,1,1,1,0], k = 2:

The final answer is 6, the window nums[4..9].

Complexity. Time O(n): exactly one pass, constant work per index. Space O(1).

Edge cases and pitfalls

• k = 0. The problem reduces to the longest run of ones; [1,0,1,1] gives 2. Nothing special is needed.
• No ones and no flips. [0,0,0] with k = 0 gives 0. Note that the optimal method must not record the window while it is invalid, otherwise it would report 1.
• k at least the number of zeros. The whole array qualifies, so the answer is n.
• Empty array. All methods return 0.
• Length formula. The window nums[l..r] holds r - l + 1 elements.
• Do not actually flip. Mutating the array is unnecessary and makes the left pointer’s bookkeeping wrong; a counter of zeros is all you need.

Related problems

• Maximum Consecutive Ones is the k = 0 special case, solvable with a single counter.
• Longest Repeating Character Replacement generalises “flip zeros” to “replace any character that is not the majority”.
• Fruit Into Baskets uses the same never-shrinking window with a different validity rule.
• Longest subarray with given sum K (positives) is another monotonic window over a non-negative array.