Longest Run of Ones After K Flips

You're given a binary array nums and an integer k — you may flip up to k zeros to ones. Return the length of the longest contiguous run of 1s you can achieve. Re-checking every possible starting point from scratch is wasteful: as the window slides forward, most of its elements stay the same. A variable-size sliding window tracks how many 0s the current window is "spending" as flips; whenever that count exceeds k, the left edge shrinks just enough to bring it back within budget, and every position is visited by each pointer at most once.

Test Case 1:

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

Output:6

Explanation:Flip the two 0s at indices 4 and 5 — the run from index 4 to index 9 becomes six 1s in a row.

Test Case 2:

Input:nums = [1, 0, 1, 1, 0, 1], k = 1

Output:4

Explanation:Flip the 0 at index 1 — the run from index 0 to index 3 becomes four 1s in a row.

Test Case 3:

Input:nums = [0, 0, 0, 1], k = 4

Output:4

Explanation:k is large enough to flip every 0 — the whole array becomes one run of 1s.

Constraints

◆1 ≤ nums.length ≤ 10⁵
◆nums[i] is either 0 or 1
◆0 ≤ k ≤ nums.length

🚀

Try the Dry Run

Don't just read the solution — watch it execute, one step at a time.

🧪Try your own test case

nums (0s and 1s) — 2-15 values, each 0 or 1k (max flips) — 0 to nums.length

1	class Solution {
2	public int longestRunOfOnesAfterKFlips(int[] nums, int k) {
3	int left = 0, zeros = 0, maxLen = 0;
4	for (int right = 0; right < nums.length; right++) {
5	if (nums[right] == 0) zeros++;
6	while (zeros > k) {
7	if (nums[left] == 0) zeros--;
8	left++;
9	}
10	maxLen = Math.max(maxLen, right - left + 1);
11	}
12	return maxLen;
13	}
14	}
15

1

0

1

0

1

2

3

4

5

6

7

8

9

10

↑left

Variables

left0

zeros0

maxLen0

INITIALIZE

Start left at 0, zeros used at 0, and maxLen at 0. Grow the window from the right, one index at a time.

Step 1 / 26

Approach & Solutions

Brute Force

Brute

For every possible start index, expand as far right as possible while counting how many 0s have been used as flips. Stop expanding the moment a further flip would exceed k, and track the longest reach seen. Correct, but every start index re-walks ground the one before it already covered.

TimeO(n²)

SpaceO(1)

Java

Try it out

class Solution {
    public int longestRunOfOnesAfterKFlips(int[] nums, int k) {
        int maxLen = 0;
        for (int i = 0; i < nums.length; i++) {
            int zeros = 0;
            int j = i;
            while (j < nums.length) {
                if (nums[j] == 0) zeros++;
                if (zeros > k) break;
                j++;
            }
            maxLen = Math.max(maxLen, j - i);
        }
        return maxLen;
    }
}

Optimal — Sliding Window

Optimal

Grow a window from the right, counting the 0s inside it. Whenever that count goes over k, shrink from the left until it's back within budget — every index still only ever moves forward, so the whole scan is a single O(n) pass. The window's length after each step is a candidate answer.

TimeO(n)