Maximum Consecutive 1's When You Can Flip K Zeros

Maximum Consecutive 1's When You Can Flip K Zeros

Imagine you have a row of light switches, and each switch is either on (1) or off (0). You want the longest unbroken stretch of switches that are all on. The twist: you are allowed to turn on at most k switches that are currently off. Your goal is to find the length of the longest run of 1's you can create using those flips.

The problem in plain words

You are given:

• A binary array arr — an array where every number is either 0 or 1.
• A number k — the most zeros you are allowed to flip into ones.

You must return the maximum number of consecutive 1's you can get after flipping at most k of the 0's.

"Consecutive" simply means the 1's must sit next to each other in the array, with no 0 left between them.

Walking through the examples

Example 1

arr = [1, 1, 1, 0, 0, 0, 1, 1, 1, 1, 0],  k = 1
Output: 5

Here you can flip only one zero. Look at the part ..., 1, 1, 1, 1, 0 near the end. There are four 1's in a row, and right after them is a single 0. If you flip that last 0 into a 1, those four 1's plus the flipped one give you 5 consecutive ones. You cannot do better, because every other group of 1's has too many 0's around it to bridge with just one flip.

Example 2

arr = [1, 1, 1, 0, 1, 0, 1, 1, 1, 0, 0],  k = 2
Output: 9

Now you can flip two zeros. Look at the stretch from the start up to index 8: 1, 1, 1, 0, 1, 0, 1, 1, 1. Inside this stretch there are exactly two 0's (at index 3 and index 5). Since k = 2, you are allowed to flip both of them. After flipping, that whole stretch becomes nine 1's in a row, so the answer is 9.

The key idea: think about a "window"

The smart way to think about this is to look at a window — a continuous slice of the array — and ask a simple question:

> Inside this window, how many 0's are there?

If the window holds k or fewer zeros, then it is a *valid* window: you can flip all those zeros and make the entire window into 1's. The length of that window is a possible answer.

So the real task becomes: find the longest window that contains no more than k zeros.

How to search for that window

A clean way to do this is the sliding window technique. The idea:

1. Move a right edge forward through the array, one element at a time. Each time it lands on a 0, count that zero.
2. If the number of zeros inside the window goes above k, the window is too "expensive" — you do not have enough flips. So move the left edge forward to shrink the window, and if the element you leave behind is a 0, subtract it from your zero count.
3. At every step, the window between left and right is always valid (at most k zeros), so check its length and keep track of the largest one you have seen.

This way each element is looked at only a couple of times, which makes the solution fast even for very large arrays.

The function you will write

The starter code gives you the function to complete:

class Solution {
public:
    int consecutiveOnesWithKFlips(vector<int> arr, int k) {
    }
};

You take in the array arr and the integer k, then return one number: the longest run of consecutive 1's you can achieve.

Things to remember

• k can be 0. In that case you cannot flip anything, so the answer is just the longest run of 1's already present.
• An array full of 1's simply returns its own length, since no flips are needed.
• The window does not have to use all k flips — it only must not need *more* than k.