Max Consecutive Ones III

Find the longest run of 1s you can make by flipping at most k zeros: a sliding window that may hold at most k zeros.

The idea

Flipping at most k zeros turns a window into all 1s exactly when the window holds at most k zeros. So the question becomes: the longest window with zeros <= k. Grow on the right counting zeros; when there are too many, move the left edge until a zero leaves.

Code

public static int LongestOnes(int[] nums, int 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--;
            left++;
        }
        best = Math.Max(best, right - left + 1);
    }
    return best;
}

Tips

• You never actually flip anything: counting zeros inside the window is enough.
• Same shape as Longest Repeating Character Replacement, where "letters that are not the top letter" play the role of zeros.
• With k = 0 this becomes Max Consecutive Ones: the longest run of 1s.

In the .NET library

Everything is plain int arithmetic over the array; no collections are needed, so the space is O(1).