Max Consecutive Ones III

medium array sliding window

Problem

Given an array A of 0s and 1s, we may change up to K values from 0 to 1. Return the length of the longest (contiguous) subarray that contains only 1s.

Inputnums = [1,1,0,1,0,0,1,1,1], k = 2

Output6

Flip the two zeros at indices 2 and 4 (or 4 and 5) to get a run of length 6.

nums (binary, comma-separated)

def longest_ones(nums, k):
    l = zeros = best = 0
    for r, x in enumerate(nums):
        if x == 0: zeros += 1
        while zeros > k:
            if nums[l] == 0: zeros -= 1
            l += 1
        if r - l + 1 > best: best = r - l + 1
    return best

function longestOnes(nums, k) {
  let l = 0, zeros = 0, best = 0;
  for (let r = 0; r < nums.length; r++) {
    if (nums[r] === 0) zeros++;
    while (zeros > k) {
      if (nums[l] === 0) zeros--;
      l++;
    }
    if (r - l + 1 > best) best = r - l + 1;
  }
  return best;
}

class Solution {
    public int longestOnes(int[] nums, int k) {
        int l = 0, zeros = 0, best = 0;
        for (int r = 0; r < nums.length; r++) {
            if (nums[r] == 0) zeros++;
            while (zeros > k) {
                if (nums[l] == 0) zeros--;
                l++;
            }
            if (r - l + 1 > best) best = r - l + 1;
        }
        return best;
    }
}

int longestOnes(vector<int>& nums, int k) {
    int l = 0, zeros = 0, best = 0;
    for (int r = 0; r < (int)nums.size(); r++) {
        if (nums[r] == 0) zeros++;
        while (zeros > k) {
            if (nums[l] == 0) zeros--;
            l++;
        }
        if (r - l + 1 > best) best = r - l + 1;
    }
    return best;
}

Explanation

We are allowed to flip up to k zeros into ones, so the longest achievable run of 1s is just the longest window that holds at most k zeros — we'd flip those zeros.

We grow a window with the right pointer r and count the zeros inside it. While the window stays within k zeros, it is valid, and we update best with the length r - l + 1.

When the zero count exceeds k, the window is too greedy, so we advance the left pointer l, decrementing zeros whenever the element leaving was a 0, until we are back within budget.

Example: nums = [1,1,0,1,0,0,1,1,1], k = 2. A window can hold the two zeros at indices 2 and 4 (giving length 6 before a third zero forces shrinking), so the answer is 6.

This is the general version of the single-flip problem; each index is processed at most twice, keeping it linear time and constant space.

Time: O(n) Space: O(1)