Max Consecutive Ones III

Problem

You are given a binary array nums (each element is 0 or 1) and an integer k. You may change at most k of the zeros into ones. Return the length of the longest run of consecutive ones achievable after those changes.

• nums has between 1 and 100,000 entries, each 0 or 1.
• k is a non-negative integer; it may exceed the number of zeros present.

Examples

• nums = [1, 0, 1, 1, 0, 0, 1, 0, 1, 1, 1], k = 2 → 6. Flip the zeros at indices 5 and 7 to join [1] at index 6 with the trailing [1, 1, 1], giving indices 5 through 10.
• nums = [0, 1, 0, 0], k = 3 → 4. Three flips are enough to turn every zero into a one.
• nums = [1, 0, 0, 1, 1], k = 0 → 2. No flips allowed; the existing run [1, 1] is the best.

Hints

1. Instead of thinking about flipping, think about which contiguous stretches could become all ones. What is the only thing that limits a stretch?
2. A stretch qualifies when it contains at most k zeros. Does that property survive shrinking the stretch?
3. Sliding window over nums, tracking the number of zeros inside; when it exceeds k, advance the left edge until it does not.