Max Consecutive Ones III

Max Consecutive Ones III is a great window question because the window grows and shrinks. You have an array of ones and zeros. You may flip a few zeros to ones. The interviewer wants to see if you can grow a window while you have flips to spare and shrink it when you run out. That balance is the real test here.

🎯 The Problem

You get an array of 0s and 1s and a number k. Here are the rules.

• You are allowed to flip at most k zeros into ones.
• After flipping, you want the longest run of ones in a row.
• A flip turns one zero into a one. You have at most k of them.
• Return the length of that longest run.

Take the array [1, 1, 1, 0, 0, 0, 1, 1, 1, 1, 0] and k as 2. You can flip two zeros. The best choice flips the zeros at positions 3 and 4. Then positions 0 through 9 become all ones, a run of length 6. So the answer is 6.

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

Explanation: Flip the zeros at index 3 and 4.
The longest run of ones becomes [1,1,1,1,1,1,1,1] from index 0 to 9, length 6.

Here is the idea as a picture. A window covers some stretch of the array. Inside it we count how many zeros we have flipped. The window is valid while that count stays at k or below.

The window has no fixed size here. It stretches as far as the flip budget allows.

🐢 Approach 1: Try Every Window (Brute Force)

The idea in one line: try every window and count its zeros from scratch.

The idea:

• Look at every start and every end.
• Count the zeros inside each window.
• The zero count is the flips that window would need.

How it works:

• For each window, if the zero count is k or less, the window is valid.
• Track the longest valid window.

Why it is weak:

• There are about n starts and n ends.
• For each pair you count zeros again.
• That climbs to O(n²) or worse.
• Overlapping windows recount the same zeros.

Here is the brute-force code for that idea:

def longest_ones(nums, k):
    best = 0
    for left in range(len(nums)):
        zeros = 0
        for right in range(left, len(nums)):
            if nums[right] == 0:
                zeros += 1
            if zeros <= k:
                best = max(best, right - left + 1)
    return best

⚡ Approach 2: A Growing Sliding Window (Best)

The idea in one line: grow the window while you can afford the zeros and shrink it the moment you go over budget.

The idea:

• Use a sliding window with two pointers, left and right.
• The window is everything between them.
• Keep a count of zeros inside the window. That count is your flip budget.
• The window is valid while the zero count is k or less.

How it works:

• Move right forward one step. If the new number is a zero, add one to the zero count. You spent a flip.
• If the zero count goes above k, the window is invalid.
• Then move left forward to shrink. If the number leaving was a zero, subtract one. You got a flip back.
• Keep shrinking until the count is k or less again.
• After each step the window is valid, so its length is a candidate.

Why it is fast:

• Each pointer only moves forward, at most n steps.
• No recounting of zeros.
• One clean pass, so O(n).

Here is a dry-run of the window on the example with k equal to 2. Watch how left jumps forward only when the zero count goes over 2.

Steps to Solve

1. Set left to 0 and a zero count to 0 and the best length to 0.
2. Move right from the start to the end of the array.
3. If the number at right is a zero, add one to the zero count.
4. While the zero count is greater than k, shrink. If the number at left is a zero, subtract one from the count. Then move left forward.
5. The current window length is right - left + 1. Update the best length if this is larger.
6. When right reaches the end, the best length is the answer.

#include <stdio.h>

int longestOnes(int nums[], int n, int k) {
    int left = 0, zeros = 0, best = 0;
    for (int right = 0; right < n; right++) {
        if (nums[right] == 0) zeros++;     // spent a flip
        while (zeros > k) {                // too many flips
            if (nums[left] == 0) zeros--;  // got a flip back
            left++;                        // shrink from the left
        }
        int len = right - left + 1;        // current valid window
        if (len > best) best = len;
    }
    return best;
}

int main(void) {
    int nums[] = {1, 1, 1, 0, 0, 0, 1, 1, 1, 1, 0};
    int k = 2;
    printf("%d\n", longestOnes(nums, 11, k));
    return 0;
}

6

#include <iostream>
#include <vector>
using namespace std;

int longestOnes(vector<int>& nums, int k) {
    int left = 0, zeros = 0, best = 0;
    for (int right = 0; right < (int)nums.size(); right++) {
        if (nums[right] == 0) zeros++;     // spent a flip
        while (zeros > k) {                // too many flips
            if (nums[left] == 0) zeros--;  // got a flip back
            left++;                        // shrink from the left
        }
        int len = right - left + 1;        // current valid window
        if (len > best) best = len;
    }
    return best;
}

int main() {
    vector<int> nums = {1, 1, 1, 0, 0, 0, 1, 1, 1, 1, 0};
    int k = 2;
    cout << longestOnes(nums, k) << endl;
    return 0;
}

6

public class MaxOnes {
    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++;     // spent a flip
            while (zeros > k) {                // too many flips
                if (nums[left] == 0) zeros--;  // got a flip back
                left++;                        // shrink from the left
            }
            int len = right - left + 1;        // current valid window
            if (len > best) best = len;
        }
        return best;
    }

    public static void main(String[] args) {
        int[] nums = { 1, 1, 1, 0, 0, 0, 1, 1, 1, 1, 0 };
        int k = 2;
        System.out.println(longestOnes(nums, k));
    }
}

6

def longest_ones(nums, k):
    left = 0
    zeros = 0
    best = 0
    for right in range(len(nums)):
        if nums[right] == 0:
            zeros += 1            # spent a flip
        while zeros > k:          # too many flips
            if nums[left] == 0:
                zeros -= 1        # got a flip back
            left += 1             # shrink from the left
        best = max(best, right - left + 1)  # current valid window
    return best


nums = [1, 1, 1, 0, 0, 0, 1, 1, 1, 1, 0]
k = 2
print(longest_ones(nums, k))

6

function longestOnes(nums, k) {
  let left = 0;
  let zeros = 0;
  let best = 0;
  for (let right = 0; right < nums.length; right++) {
    if (nums[right] === 0) zeros++;     // spent a flip
    while (zeros > k) {                 // too many flips
      if (nums[left] === 0) zeros--;    // got a flip back
      left++;                           // shrink from the left
    }
    best = Math.max(best, right - left + 1); // current valid window
  }
  return best;
}

const nums = [1, 1, 1, 0, 0, 0, 1, 1, 1, 1, 0];
const k = 2;
console.log(longestOnes(nums, k));

6

Let us walk through the Python version line by line and see why each line is there.

The lines left = 0, zeros = 0, best = 0 set up the start. left is the left edge of the window. zeros counts how many zeros are inside the window right now. best holds the longest valid window we have seen.

The loop for right in range(len(nums)) moves the right edge forward one step at a time. right is the new number entering the window.

The lines if nums[right] == 0: zeros += 1 spend a flip. When the entering number is a zero, we would have to flip it. So we add one to the zero count.

The loop while zeros > k checks the budget. If we have used more than k flips, the window is invalid. So we shrink. The line if nums[left] == 0: zeros -= 1 gives a flip back when the number leaving on the left is a zero. The line left += 1 moves the left edge forward, shrinking the window. We keep shrinking until the count is k or less.

The line best = max(best, right - left + 1) measures the current window. The length is right - left + 1. Right after the while loop the window is always valid. So we compare its length with the best so far and keep the larger.

The line return best gives the answer once right has passed the whole array.

⏱️ Time and Space Complexity

The brute force tries every window, so it is slow and recounts zeros over and over. The sliding window moves each pointer forward only. Each pointer takes at most n steps. So it runs in one pass. That takes the time from O(n²) down to O(n). We keep just a few counters, so the extra space is O(1).

🧩 Key Takeaways

• ✅ Treat k as a flip budget, which is the number of zeros you are allowed to keep inside the window.
• ✅ Grow the window by moving the right pointer, and shrink it by moving the left pointer.
• ✅ The window is valid while the zero count stays at k or below.
• ✅ Right after shrinking, the window is valid, so its length is a candidate for the answer.
• ✅ Each pointer moves forward only, so the whole scan is O(n) time and O(1) space.

🚀 What’s Next?

• Find All Anagrams in a String
• Longest Continuous Subarray With Absolute Diff Less Than or Equal to Limit