Max Consecutive Ones III: Sliding Window Allowing At Most K Zero Flips

• Max Consecutive Ones III – find the longest run of consecutive 1s obtainable in a binary array if you may flip at most K zeros to ones.
• Variable sliding window – grow the right edge counting zeros; shrink the left edge when the zero count exceeds K.
• No actual flip – any window with at most K zeros can be turned into all ones by flipping those zeros, so counting is sufficient.
• K=0 case – reduces to the plain Max Consecutive Ones problem with the count-and-reset approach.
• Complexity – O(n) time and O(1) space because both pointers only move forward.

What is the Max Consecutive Ones III problem?

Given a binary array and an integer K, find the maximum number of consecutive 1s in the array if you can flip at most K zeros to ones. The key insight is that you never actually flip anything: any window containing at most K zeros can be turned into all ones by flipping exactly those zeros.

package com.bank.service;

public class MaxConsecutiveOnesIII {
    public static 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;
    }

    public static void main(String[] args) {
        int[] uptime = {1, 1, 0, 1, 1, 1, 0, 1, 0, 1};
        System.out.println("Longest with K=2 flips: " + longestOnes(uptime, 2));
    }
}

Longest with K=2 flips: 8

Why is no actual flipping needed?

The window width directly represents the achievable run length. Any window containing at most K zeros can become an unbroken run of ones by flipping those K or fewer zeros. So counting zeros in the window is all you need. The problem becomes: find the widest window with at most K zeros.

// Reframing:
// "Longest run of 1s with at most K flips"
// equals
// "Widest window containing at most K zeros"
//
// No flip array needed, just a zero counter

How does the sliding window maintain the invariant?

The invariant is: the window [left, right] never contains more than K zeros. When a new zero enters from the right and pushes the count above K, the left edge shrinks until a zero is pushed out, restoring the invariant.

// Walkthrough: nums = [1,1,0,1,1,1,0,1,0,1], K=2
// right=0: val=1, zeros=0, window=[0,0], best=1
// right=1: val=1, zeros=0, window=[0,1], best=2
// right=2: val=0, zeros=1, window=[0,2], best=3
// right=3: val=1, zeros=1, window=[0,3], best=4
// right=4: val=1, zeros=1, window=[0,4], best=5
// right=5: val=1, zeros=1, window=[0,5], best=6
// right=6: val=0, zeros=2, window=[0,6], best=7
// right=7: val=1, zeros=2, window=[0,7], best=8
// right=8: val=0, zeros=3 > 2
//   shrink: left=0 (val=1), zeros=3, left=1
//   shrink: left=1 (val=1), zeros=3, left=2
//   shrink: left=2 (val=0), zeros=2, left=3
//   window=[3,8], best=8
// right=9: val=1, zeros=2, window=[3,9], best=max(8,7)=8
// Answer: 8

How is this different from plain Max Consecutive Ones?

The plain problem is the K=0 special case. With K=0, the window can contain no zeros at all, so it reduces to counting the longest run of ones with a simple counter.

| Aspect | Max Consecutive Ones | Max Consecutive Ones III |
|---|---|---|
| Flip budget | 0 | K |
| Technique | Count-and-reset | Sliding window with zero counter |
| Window | Implicit | Explicit with left and right pointers |
| Time | O(n) | O(n) |
| Space | O(1) | O(1) |

// K=0 version is just count-and-reset:
int current = 0, best = 0;
for (int num : nums) {
    if (num == 1) { current++; best = Math.max(best, current); }
    else current = 0;
}

// K>0 version is the sliding window:
// longestOnes(nums, 0) gives the same result as count-and-reset

What about the non-shrinking window variant?

A slight variation keeps the window non-shrinking: instead of shrinking to restore validity, you only advance left by one when the zero budget is exceeded. This means the window never shrinks, only grows or stays the same size, and the final window width is the answer.

package com.bank.service;

public class MaxOnesNonShrinking {
    public static int longestOnes(int[] nums, int k) {
        int left = 0, zeros = 0;
        for (int right = 0; right < nums.length; right++) {
            if (nums[right] == 0) zeros++;
            if (zeros > k) {
                if (nums[left] == 0) zeros--;
                left++;
            }
        }
        return nums.length - left;
    }
}
// Both versions are O(n); the non-shrinking one is slightly faster
// but the explicit shrink version is clearer for explaining the invariant.

What are the edge cases?

If K is zero, the answer is the longest run of ones without any flips. If K is greater than or equal to the number of zeros in the array, the answer is the full array length. An all-ones array returns the full length regardless of K.

package com.bank.service;

public class MaxOnesEdgeCases {
    public static void main(String[] args) {
        System.out.println(MaxConsecutiveOnesIII.longestOnes(new int[]{1,1,1}, 2));   // 3
        System.out.println(MaxConsecutiveOnesIII.longestOnes(new int[]{0,0,0}, 3));   // 3
        System.out.println(MaxConsecutiveOnesIII.longestOnes(new int[]{0,0,0}, 2));   // 2
        System.out.println(MaxConsecutiveOnesIII.longestOnes(new int[]{}, 5));         // 0
    }
}

3
3
2
0

What are common mistakes?

The most common mistake is physically flipping zeros in the array and then trying to unflip them. This is unnecessary complexity and prone to bugs. The counting approach is simpler and correct.

// WRONG: physically flipping zeros
nums[right] = 1;   // flip to 1
// Later: nums[left] = 0;  // unflip? which one was originally 0?
// This is error-prone and unnecessary

// CORRECT: just count zeros
if (nums[right] == 0) zeros++;
// No modification to the array

How does this generalize?

The same window structure solves "longest substring with at most K character replacements." Replace the zero counter with a count of the most frequent character in the window; if the window size minus the max-frequency count exceeds K, shrink. The principle is identical: the window budget constrains how many elements you may change.

// Longest substring with at most K replacements:
// Window [left, right], freq[] tracks character counts
// maxFreq = max frequency of any single character in window
// If (right - left + 1 - maxFreq) > k, shrink from left
// The longest valid window is the answer

When should you use this technique?

Use this whenever the problem asks for the longest subarray satisfying a constraint after allowing at most K modifications. In banking, this applies to computing SLA uptime with excused outages or finding the longest compliant period if a small number of violations are forgiven.

package com.bank.service;

public class UptimeWithExcusedOutages {
    public static void main(String[] args) {
        // Daily uptime: 1=up, 0=down
        int[] uptime = {1,1,0,1,0,1,1,1,0,1,1,0,1,1,1,1};
        int excusedDays = 3;
        int longestUp = MaxConsecutiveOnesIII.longestOnes(uptime, excusedDays);
        System.out.println("Longest uptime with " + excusedDays + " excused: " + longestUp + " days");
    }
}

Longest uptime with 3 excused: 14 days

What should a senior engineer know?

A senior engineer should explain that this is a general pattern: the window budget constrains modifications, and counting those modifications (zeros, character replacements, etc.) is always sufficient. The non-shrinking variant is a minor optimization. The K=0 reduction to plain Max Consecutive Ones shows understanding of the problem family.

What are common interview follow-up questions?

• Interviewers commonly ask:
• Do you need to actually flip? (No, just count zeros in the window.)
• What if K=0? (Reduces to plain Max Consecutive Ones.)
• Time and space? (O(n) time, O(1) space.)
• What about longest substring with K replacements? (Same structure with a frequency map.)