Max Consecutive Ones III

Share

Given a binary array nums and integer k, return the maximum number of consecutive 1s if 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], k=3 → Output: 10

Solution Approach

Sliding window with a count of zeros in current window. Expand right; if zeros in window > k, shrink from left.

  • Maintain left pointer and zeros count.
  • Expand right: if nums[right]==0, increment zeros.
  • While zeros > k: if nums[left]==0 decrement zeros; increment left.
  • Answer = max(right - left + 1).
Java
class Solution {
    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)