Longest Subarray with Ones after Replacement (Max Consecutive Ones III)

• This problem asks for the longest window in a binary array that becomes all ones after flipping at most k zeros.
• A variable-size sliding window counts how many zeros lie inside the window.
• The right pointer expands the window; when the zero count exceeds k, the left pointer shrinks it.
• You only need the count of zeros, not their positions, because all flips cost the same.
• The widest feasible window ever seen is the answer.
• Time is O(N) and space is O(1).

What is the Longest Subarray with Ones after Replacement problem?

Given a binary array of 0s and 1s and an integer k, find the length of the longest contiguous subarray that contains only 1s after you flip at most k zeros to ones. This is LeetCode 1004 (Max Consecutive Ones III).

For example, given [1, 1, 0, 0, 1, 1, 1, 0, 1] and k = 2, the longest window is 7 (flip the zeros at indices 2 and 7).

How does the sliding window work?

We keep a window with left and right boundaries and a counter for how many zeros are inside. The right pointer walks across the array. Each time it lands on a zero, we increment the counter. When the counter exceeds k, we shrink from the left until the counter returns to k.

package com.bank.service;

public class LongestOnesService {

    /**
     * Finds the longest on-time payment streak achievable
     * after forgiving at most k missed payments.
     * Used by the National Bank of India loan-servicing team.
     */
    public static int longestOnes(int[] history, int k) {
        int left = 0;
        int zeros = 0;
        int best = 0;

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

    public static void main(String[] args) {
        int[] history = {1, 1, 0, 0, 1, 1, 1, 0, 1};
        int k = 2;
        System.out.println("Longest clean streak with "
            + k + " waivers: " + longestOnes(history, k));
    }
}

javac -d out com/bank/service/LongestOnesService.java
java -cp out com.bank.service.LongestOnesService

Longest clean streak with 2 waivers: 7

Why does only the zero count matter?

The key insight is that you never need to track which specific zeros to flip. Any k zeros inside the window can be flipped, and the cost is identical regardless of which ones you choose. This collapses what looks like a combinatorial choice into a plain single-counter window problem.

Why is the while loop sometimes replaced with an if?

Since the zero count only goes one over budget at a time (each step adds at most one zero), a single if that advances left once per expansion is sufficient. This variation keeps the window size monotonically non-decreasing, which is slightly different behavior but gives the same final answer.

// Alternative: non-shrinking window variant
for (int right = 0; right < history.length; right++) {
    if (history[right] == 0) zeros++;
    if (zeros > k) {
        if (history[left] == 0) zeros--;
        left++;
    }
    best = Math.max(best, right - left + 1);
}

What are the edge cases?

Several edge cases deserve attention.

• All ones: no zeros to flip, the answer is the array length.
• All zeros with k >= length: flip everything, the answer is the array length.
• All zeros with k = 0: cannot flip any, the answer is 0.
• k larger than the number of zeros: the answer is the full array length.
• Empty array: the answer is 0.

package com.bank.core;

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

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

3
3
0
0

What is the time and space complexity?

Time is O(N) because the right pointer advances N times and the left pointer only moves forward, so together they take at most 2N steps. Space is O(1): a single integer counter and two index variables, regardless of input size.

How is this similar to other sliding window problems?

This is the same template as the "Longest Substring with K Replacements" string problem. The only difference is the validity condition: here it is a zero count against k; there it is the count of non-majority characters against k.

| Problem | Array type | Validity condition |
|---|---|---|
| Max Consecutive Ones III | Binary array | zeros <= k |
| Longest Substring K Replacements | Character array | non-majority chars <= k |
| Longest Subarray with Sum <= K | Positive int array | sum <= k |

Can this be used in a streaming scenario?

Yes. Because the state is a single integer counter and two pointers, this algorithm can run as a streaming computation. As new payment events arrive for each loan, you update the window incrementally without re-scanning the history. The constant space makes it safe under very long histories.

What should a senior engineer know?

A senior engineer should understand these deeper aspects.

• Non-shrinking variant: using if instead of while keeps the window size monotonically non-decreasing, which can be slightly faster but changes the invariant.
• Binary search alternative: for each right endpoint, binary search for the leftmost position such that the window has at most k zeros, using a prefix-sum array. This is O(N log N) and uses more space but demonstrates a different technique.
• Batch processing: in production, the linear window lets nightly batches recompute eligibility across millions of active loans within tight SLA windows.