DSA-028 · Exact zero-budget variable window

Longest Ones with at Most K Flips

Intermediate · Java 21 · Version 1 · editorial draft

Java reference and baseline verified on JDK 21: 10244 deterministic checks. Learner drafts are not executed.

Understand the problem

Return the longest contiguous binary subarray that becomes all ones after changing at most k zeros to ones.

nums is non-null with 0–100,000 entries, each 0 or 1. k is a nonnegative int up to Integer.MAX_VALUE. Both methods throw IllegalArgumentException for other values or negative k; null is outside the contract.
Return a length only, preserving nums. Flips are hypothetical, affect distinct zero positions, and are optional up to k. Empty input returns 0; k may exceed the number of zeros.
zeros exactly counts zeros in the current interval. Unlike historical-frequency Character Replacement, this implementation shrinks until the current window is truly feasible before updating best.

Examples

Input: nums=[1,1,0,0,1,1,1,0], k=1
Output: 4
Indices 3..6 contain one zero and three ones, so one flip yields length four.
Input: nums=[0,0,0], k=1
Output: 1
Only one zero can be included in a feasible all-ones result.

Before you start

Contiguous windows, inclusive bounds, and empty intervals
Java frequency arrays and loop-invariant reasoning

Recognize the structure

The exact number of required flips is the zero count. Adding positions cannot decrease that cost; remove left positions until the budget holds, then record the longest feasible window ending at the current right.

Try before revealing

Hint 1

What exact count determines the flips needed for one binary window?

Hint 2

Which outgoing values actually free budget?

Hint 3

Track zeros, shrink while over budget, then maximize the valid length.

Derive the solution

Reveal the baseline, optimized reasoning, and Java code

Count zero cost for every interval

Enumerate each start and end with a running zero count, recording lengths with at most k zeros. For [1,0,1],k=0, only the two single-one intervals qualify; with k=1 the full length three qualifies. This O(n²) baseline uses O(1) workspace and directly expresses the budget predicate.

Improve the baseline

Track the entering zero

Increment zeros only when nums[right]==0. Ones extend length at no budget cost.

Restore exact feasibility

While zeros>k, move left past values, decrementing zeros only when the outgoing value is zero. Removing a one may not repair the budget, so one removal is not always enough.

Record a valid window

After contraction, update best from right-left+1. The retained window is genuinely feasible and left is the earliest still-useful boundary for this right.

Why it is correct

Exact state

zeros equals the count of zero values in nums[left..right]. Entry and exit adjust it only for actual zeros. The validation scan ensures this predicate represents the stated binary flip cost.

Safe contraction

A window with more than k zeros cannot be repaired by adding more values. Discarding its left boundary loses no future feasible window beginning there until enough zeros are removed. All starts passed during contraction still exceed the budget at that moment.

Maximum and termination

For every right, the retained earliest feasible left gives the longest useful feasible suffix; previously discarded starts cannot yield a missed optimum. Every recorded length is achievable with at most k flips. Both pointers move forward at most n times, proving correctness and linear work.

Complete Java reference and baseline

Save as Solution.java. Node definitions and imports are included where needed. The baseline is included for comparison; respect its input-size limits.

public final class Solution {
    private static void validate(int[] nums, int k) {
        if (k < 0) throw new IllegalArgumentException("k must be nonnegative");
        for (int value : nums) if (value != 0 && value != 1) throw new IllegalArgumentException("binary input required");
    }
    public static int longestOnes(int[] nums, int k) {
        validate(nums, 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--;
            best = Math.max(best, right - left + 1);
        }
        return best;
    }
    public static int baseline(int[] nums, int k) {
        validate(nums, k);
        int best = 0;
        for (int start = 0; start < nums.length; start++) {
            int zeros = 0;
            for (int end = start; end < nums.length; end++) {
                if (nums[end] == 0) zeros++;
                if (zeros <= k) best = Math.max(best, end - start + 1);
            }
        }
        return best;
    }
}

Read the meaningful blocks

Validate the binary alphabet

The cost 1-value is meaningful only for 0/1. Reject other integers consistently before scanning.

while, not one shrink

For [1,1,0],k=0, removing the two leading ones does not reduce zeros; keep shrinking through the zero.

No physical flips

The input stays unchanged. Count the zeros that would need changes instead of writing ones into the array.

Complexity

O(n) time including validation, one expansion scan and at most n total left removals. O(1) auxiliary space, with no separate output array.

The interval-count baseline is O(n²) time and O(1) space. Tests independently enumerate intervals and their flip costs, cover k=0 and huge budgets, and verify preservation of the input.

Exact-state walkthroughs

Reveal normal and boundary traces

Remove ones until an outgoing zero frees budget

Input: {"nums":[1,1,0,0,1,1,1,0],"k":1} · Result: 4

Step 1 of 22: Validate the input and initialize the empty interval.

The declared value domain makes the window cost monotone under expansion.

Original input — highlighted current interval

0: 1
1: 1
2: 0
3: 0
4: 1
5: 1
6: 1
7: 0

Current zero count: 0. Flip budget: 1. The scan restores the budget before recording a length.

State after this step
Variable	Value
values	`[1,1,0,0,1,1,1,0]`
left	`0`
right	`-1`
zeros	`0`
k	`1`
best	`0`

See the affected Java block

 1 public final class Solution {
 2     private static void validate(int[] nums, int k) {
 3         if (k < 0) throw new IllegalArgumentException("k must be nonnegative");
 4         for (int value : nums) if (value != 0 && value != 1) throw new IllegalArgumentException("binary input required");
 5     }
 6     public static int longestOnes(int[] nums, int k) {
 7         validate(nums, k);
 8         int left = 0, zeros = 0, best = 0;
 9         for (int right = 0; right < nums.length; right++) {
10             if (nums[right] == 0) zeros++;
11             while (zeros > k) if (nums[left++] == 0) zeros--;
12             best = Math.max(best, right - left + 1);
13         }
14         return best;
15     }
16     public static int baseline(int[] nums, int k) {
17         validate(nums, k);
18         int best = 0;
19         for (int start = 0; start < nums.length; start++) {
20             int zeros = 0;
21             for (int end = start; end < nums.length; end++) {
22                 if (nums[end] == 0) zeros++;
23                 if (zeros <= k) best = Math.max(best, end - start + 1);
24             }
25         }
26         return best;
27     }
28 }
29

Highlight locates the relevant statement or block; one trace step may summarize several assignments.

Read the full static trace

Validate the input and initialize the empty interval.
The declared value domain makes the window cost monotone under expansion.
values
[1,1,0,0,1,1,1,0]
left
0
right
-1
zeros
0
k
1
best
0
Include the next input occurrence.
The running sum or zero count describes exactly the current interval.
values
[1,1,0,0,1,1,1,0]
left
0
right
0
zeros
0
k
1
best
0
Record the genuinely feasible window length.
The exact zero count is within budget before this length is judged.
values
[1,1,0,0,1,1,1,0]
left
0
right
0
zeros
0
k
1
best
1
Include the next input occurrence.
The running sum or zero count describes exactly the current interval.
values
[1,1,0,0,1,1,1,0]
left
0
right
1
zeros
0
k
1
best
1
Record the genuinely feasible window length.
The exact zero count is within budget before this length is judged.
values
[1,1,0,0,1,1,1,0]
left
0
right
1
zeros
0
k
1
best
2
Include the next input occurrence.
The running sum or zero count describes exactly the current interval.
values
[1,1,0,0,1,1,1,0]
left
0
right
2
zeros
1
k
1
best
2
Record the genuinely feasible window length.
The exact zero count is within budget before this length is judged.
values
[1,1,0,0,1,1,1,0]
left
0
right
2
zeros
1
k
1
best
3
Include the next input occurrence.
The running sum or zero count describes exactly the current interval.
values
[1,1,0,0,1,1,1,0]
left
0
right
3
zeros
2
k
1
best
3
Move left until the zero budget is restored.
Removing a one does not free a flip; continue until zeros is at most k.
values
[1,1,0,0,1,1,1,0]
left
1
right
3
zeros
2
k
1
best
3
outgoing
1
Move left until the zero budget is restored.
Removing a one does not free a flip; continue until zeros is at most k.
values
[1,1,0,0,1,1,1,0]
left
2
right
3
zeros
2
k
1
best
3
outgoing
1
Move left until the zero budget is restored.
Removing a one does not free a flip; continue until zeros is at most k.
values
[1,1,0,0,1,1,1,0]
left
3
right
3
zeros
1
k
1
best
3
outgoing
0
Record the genuinely feasible window length.
The exact zero count is within budget before this length is judged.
values
[1,1,0,0,1,1,1,0]
left
3
right
3
zeros
1
k
1
best
3
Include the next input occurrence.
The running sum or zero count describes exactly the current interval.
values
[1,1,0,0,1,1,1,0]
left
3
right
4
zeros
1
k
1
best
3
Record the genuinely feasible window length.
The exact zero count is within budget before this length is judged.
values
[1,1,0,0,1,1,1,0]
left
3
right
4
zeros
1
k
1
best
3
Include the next input occurrence.
The running sum or zero count describes exactly the current interval.
values
[1,1,0,0,1,1,1,0]
left
3
right
5
zeros
1
k
1
best
3
Record the genuinely feasible window length.
The exact zero count is within budget before this length is judged.
values
[1,1,0,0,1,1,1,0]
left
3
right
5
zeros
1
k
1
best
3
Include the next input occurrence.
The running sum or zero count describes exactly the current interval.
values
[1,1,0,0,1,1,1,0]
left
3
right
6
zeros
1
k
1
best
3
Record the genuinely feasible window length.
The exact zero count is within budget before this length is judged.
values
[1,1,0,0,1,1,1,0]
left
3
right
6
zeros
1
k
1
best
4
Include the next input occurrence.
The running sum or zero count describes exactly the current interval.
values
[1,1,0,0,1,1,1,0]
left
3
right
7
zeros
2
k
1
best
4
Move left until the zero budget is restored.
Removing a one does not free a flip; continue until zeros is at most k.
values
[1,1,0,0,1,1,1,0]
left
4
right
7
zeros
1
k
1
best
4
outgoing
0
Record the genuinely feasible window length.
The exact zero count is within budget before this length is judged.
values
[1,1,0,0,1,1,1,0]
left
4
right
7
zeros
1
k
1
best
4
Return the contract result.
The result follows the declared empty, ordering, tie, and mutation rules.
result
4

No flips allowed

Input: {"nums":[1,1,0],"k":0} · Result: 2

Step 1 of 11: Validate the input and initialize the empty interval.

The declared value domain makes the window cost monotone under expansion.

Original input — highlighted current interval

0: 1
1: 1
2: 0

Current zero count: 0. Flip budget: 0. The scan restores the budget before recording a length.

State after this step
Variable	Value
values	`[1,1,0]`
left	`0`
right	`-1`
zeros	`0`
k	`0`
best	`0`

See the affected Java block

 1 public final class Solution {
 2     private static void validate(int[] nums, int k) {
 3         if (k < 0) throw new IllegalArgumentException("k must be nonnegative");
 4         for (int value : nums) if (value != 0 && value != 1) throw new IllegalArgumentException("binary input required");
 5     }
 6     public static int longestOnes(int[] nums, int k) {
 7         validate(nums, k);
 8         int left = 0, zeros = 0, best = 0;
 9         for (int right = 0; right < nums.length; right++) {
10             if (nums[right] == 0) zeros++;
11             while (zeros > k) if (nums[left++] == 0) zeros--;
12             best = Math.max(best, right - left + 1);
13         }
14         return best;
15     }
16     public static int baseline(int[] nums, int k) {
17         validate(nums, k);
18         int best = 0;
19         for (int start = 0; start < nums.length; start++) {
20             int zeros = 0;
21             for (int end = start; end < nums.length; end++) {
22                 if (nums[end] == 0) zeros++;
23                 if (zeros <= k) best = Math.max(best, end - start + 1);
24             }
25         }
26         return best;
27     }
28 }
29

Highlight locates the relevant statement or block; one trace step may summarize several assignments.

Read the full static trace

Validate the input and initialize the empty interval.
The declared value domain makes the window cost monotone under expansion.
values
[1,1,0]
left
0
right
-1
zeros
0
k
0
best
0
Include the next input occurrence.
The running sum or zero count describes exactly the current interval.
values
[1,1,0]
left
0
right
0
zeros
0
k
0
best
0
Record the genuinely feasible window length.
The exact zero count is within budget before this length is judged.
values
[1,1,0]
left
0
right
0
zeros
0
k
0
best
1
Include the next input occurrence.
The running sum or zero count describes exactly the current interval.
values
[1,1,0]
left
0
right
1
zeros
0
k
0
best
1
Record the genuinely feasible window length.
The exact zero count is within budget before this length is judged.
values
[1,1,0]
left
0
right
1
zeros
0
k
0
best
2
Include the next input occurrence.
The running sum or zero count describes exactly the current interval.
values
[1,1,0]
left
0
right
2
zeros
1
k
0
best
2
Move left until the zero budget is restored.
Removing a one does not free a flip; continue until zeros is at most k.
values
[1,1,0]
left
1
right
2
zeros
1
k
0
best
2
outgoing
1
Move left until the zero budget is restored.
Removing a one does not free a flip; continue until zeros is at most k.
values
[1,1,0]
left
2
right
2
zeros
1
k
0
best
2
outgoing
1
Move left until the zero budget is restored.
Removing a one does not free a flip; continue until zeros is at most k.
values
[1,1,0]
left
3
right
2
zeros
0
k
0
best
2
outgoing
0
Record the genuinely feasible window length.
The exact zero count is within budget before this length is judged.
values
[1,1,0]
left
3
right
2
zeros
0
k
0
best
2
Return the contract result.
The result follows the declared empty, ordering, tie, and mutation rules.
result
2

Test the contract

Input: nums=[], k=3
Output: 0
No elements.
Input: nums=[1,1,0], k=0
Output: 2
No flips allowed.
Input: nums=[0,0], k=10
Output: 2
Unused budget is allowed.
Input: nums=[1,2], k=1
Output: IllegalArgumentException
Input must be binary.

Common mistakes and counterexamples

Decrease zeros on every removal

Counterexample: Removing a one from [1,0] does not free a flip.

Decrement only if the outgoing value is zero.

Shrink once and record an invalid window

Counterexample: [1,1,0],k=0 still violates the budget after removing one leading one.

Use while zeros>k before updating best.

Interpret the budget as exactly k

Counterexample: [1,1],k=5 still has a valid answer of two using no flips.

Allow any number from zero through k.

Follow-ups

Return positions to flip.

Save best boundaries, then scan that interval for zeros. This needs O(z) output for the z selected flips; do not mutate the original array to produce a witness.

Require exactly k zero-to-one flips.

A selected interval must contain exactly k zeros if flips must occur inside it. The at-most result can differ when fewer than k zeros exist; define infeasibility and use an exact-count objective rather than relabeling this answer.

Replace flips with another additive budget.

The same window reasoning works when every element contributes a nonnegative cost. Signed costs can decrease on expansion, so the monotonic rejection argument may fail and require prefix-state methods.

Your Java attempt

Java 21 · Draft only. Your code is not compiled, executed, or graded here. Run it locally against the examples and edge cases.

Saving stores text in this browser, visible to other people using this browser profile. It does not sync to your account. Loading is always explicit.

Approach, code, and test notes (20,000 characters maximum)

No unsaved text changes · 92/20,000 characters

Self-review

I maintain an exact zero count.I shrink until the current window is feasible.I preserve input and allow unused budget.

Use the checklist to test your explanation. Checks apply to this visit.

Related foundations

Sliding windows: define validity first

Keep practicing

Open focused practice

AceYourInterviews · 2026-10-15 · Original teaching content, examples, and Java implementations authored for AceYourInterviews. These standard algorithmic tasks carry no company-frequency or interview-outcome claims.