Max Consecutive Ones III

Share

Find maximum consecutive 1s given you can flip at most K zeros.

Example 1
Input: nums=[1,1,1,0,0,0,1,1,1,1,0], k=2 → Output: 6
Example 2
Input: nums=[0,0,1,1,0,0,1,1,1,0,1,1,0,0,0,1,1,1,1,0], k=3 → Output: 10

Solution Approach

Sliding window: expand right, shrink left when zeros in window exceed K.

  • Two pointers left and right
  • Count zeros in window
  • When zeros > k: if nums[left]==0 decrement zeros, move left++
  • Track max window size
Java
public int longestOnes(int[] nums, int k) {
    int left = 0, zeros = 0, max = 0;
    for (int right = 0; right < nums.length; right++) {
        if (nums[right] == 0) zeros++;
        while (zeros > k) {
            if (nums[left] == 0) zeros--;
            left++;
        }
        max = Math.max(max, right - left + 1);
    }
    return max;
}
  • Time Complexity: O(n)
  • Space Complexity: O(1)