Max Consecutive ones

Problem Link

Max Consecutive Ones III – LeetCode #1004

Problem Statement

You are given a binary array nums (containing only 0s and 1s) and an integer k.

Your task is to return the maximum number of consecutive 1's in the array if you can flip at most k 0's to 1's.

Examples

• Input: nums = [1,1,1,0,0,0,1,1,1,1,0], k = 2
  Output: 6
  Explanation: Flipping the two 0s at indices 3 and 4 gives [1,1,1,1,1,1].

• 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

Constraints

• 1 <= nums.length <= 10⁵

• nums[i] ∈ {0, 1}

• 0 <= k <= nums.length

Intuition

The goal is to find the longest contiguous subarray that contains at most k zeroes (which we can flip to ones). This is a classic variable-size sliding window problem.

Key Insight:

• A valid window is one where the number of zeroes in it is less than or equal to k.

• We slide the window ([i, j]) such that we expand j, and shrink i only when the number of zeroes exceeds k.

Approach

1. Use two pointers i and j to represent the sliding window.

2. Maintain a count of zeros in the current window (zeroCount).

3. Expand the window by moving j forward.

4. If zeroCount > k, shrink the window from the left (i++) until it's valid again.

5. At every step, update the maximum window size (max = max(max, j - i + 1)).

Java Code

class Solution {
    public int longestOnes(int[] nums, int k) {
        int i = 0, j = 0;
        int max = 0;
        int zeroCount = 0;

        while (j < nums.length) {
            if (nums[j] == 0) {
                zeroCount++;
            }

            // Shrink window if zeroCount exceeds k
            while (zeroCount > k) {
                if (nums[i] == 0) {
                    zeroCount--;
                }
                i++;
            }

            max = Math.max(max, j - i + 1);
            j++;
        }

        return max;
    }
}

Time and Space Complexity

• Time Complexity: O(n)
  Each element is visited at most twice (once by j, once by i).

• Space Complexity: O(1)
  Only a few integer variables are used.

Dry Run

Input:

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

Steps:

• Start with i = 0, j = 0, zeroCount = 0

• Process elements until j = 5 → zeroCount = 3 (more than k)

• Shrink window by incrementing i → zeroCount drops to 2

• Max length updated when window becomes valid again

• Continue to process till j = 10

• Final max = 6 for window [5, 10]

Output: 6

Conclusion

This problem is a standard application of the Variable Size Sliding Window – Condition Based pattern.

It highlights the technique of:

• Expanding the window greedily.

• Shrinking it only when the condition (zero count ≤ k) is violated.

This pattern is extremely useful in problems involving:

• At most k operations allowed

• Maintaining constraints in dynamic subarrays or substrings

• Optimizing window sizes dynamically