Course4all
Join us on telegram
Home/dsa/Sliding Window/Max Consecutive Ones III

Max Consecutive Ones III

Master this topic with zero to advance depth.

Max Consecutive Ones III

Given a binary array nums and an integer k, return the maximum number of consecutive 1's in the array if you can flip at most k 0's.

Visual Representation

nums = [1,1,1,0,0,0,1,1,1,1,0], k = 2 L R | | 1 1 1 0 0 0 1 1 1 1 0 [-----] (Zeros: 1 <= 2, Expand R) L R | | 1 1 1 0 0 0 1 1 1 1 0 [-------] (Zeros: 2 <= 2, Expand R) L R | | 1 1 1 0 0 0 1 1 1 1 0 [---------] (Zeros: 3 > 2! Shrink L)
Medium

Examples

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

Level I: Brute Force

Intuition

Check every possible subarray and count the number of zeros in it. If the zero count is less than or equal to k, the subarray is valid. Keep track of the maximum length of such valid subarrays.

Thought Process

  1. Use two nested loops to define all possible subarrays [i, j].
  2. In the inner loop, count zeros.
  3. If zeros <= k, update maxLen = max(maxLen, j - i + 1).
  4. If zeros > k, break the inner loop (optimization).
⏱ O(N^2)💾 O(1)

Detailed Dry Run

ijnums[j]ZerosMax LenAction
00101Update
03014Update
04025Update
05035Break (Zeros > k)
java
public class Main {
    public static int longestOnes(int[] nums, int k) {
        int maxLen = 0;
        for (int i = 0; i < nums.length; i++) {
            int zeros = 0;
            for (int j = i; j < nums.length; j++) {
                if (nums[j] == 0) zeros++;
                if (zeros <= k) {
                    maxLen = Math.max(maxLen, j - i + 1);
                } else {
                    break;
                }
            }
        }
        return maxLen;
    }

    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
    }
}
Approach 2

Level II: Binary Search on Answer (O(N log N))

Intuition

We can binary search for the maximum possible length L of a valid subarray. For a fixed length L, we can check if there exists any subarray of length L with at most k zeros using a fixed-size sliding window in O(N)O(N) time.

Thought Process

  1. Search range for length is [0, n].
  2. For a fixed mid length:
    • Slide a window of size mid across the array.
    • Count zeros in the window.
    • If any window has zeros <= k, then mid is possible.
  3. If possible, search higher; else search lower.

Pattern: Search on Answer Space

⏱ O(N log N) - Binary search takes $\log N$ steps, and each check takes $O(N)$.💾 O(1)
java
public class Solution {
    public int longestOnes(int[] nums, int k) {
        int low = 0, high = nums.length, res = 0;
        while (low <= high) {
            int mid = low + (high - low) / 2;
            if (check(nums, k, mid)) {
                res = mid;
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }
        return res;
    }

    private boolean check(int[] nums, int k, int len) {
        int zeros = 0;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] == 0) zeros++;
            if (i >= len) {
                if (nums[i - len] == 0) zeros--;
            }
            if (i >= len - 1 && zeros <= k) return true;
        }
        return false;
    }
}
Approach 3

Level III: Optimal (Sliding Window)

Intuition

Thought Process

Instead of checking every subarray, we use a window [left, right]. We expand the window by moving right. If the number of zeros in the window exceeds k, we must shrink the window from the left until the zero count is back to k.

Pattern: Variable Size Sliding Window

  • Expand: windowSum += (nums[right] == 0 ? 1 : 0)
  • Constraint: zeros > k
  • Shrink: while (zeros > k) { if (nums[left] == 0) zeros--; left++; }
⏱ O(N)💾 O(1)

Detailed Dry Run

RNumZerosActionMax Len
301Expand4
402Expand5
503Shrink L (until zeros=2)5
1002Expand6
java
public class Main {
    public static int longestOnes(int[] nums, int k) {
        int left = 0, res = 0, zeros = 0;
        for (int right = 0; right < nums.length; right++) {
            if (nums[right] == 0) zeros++;
            while (zeros > k) {
                if (nums[left] == 0) zeros--;
                left++;
            }
            res = Math.max(res, right - left + 1);
        }
        return res;
    }

    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
    }
}

⚠️ Common Pitfalls & Tips

Be careful with the while loop condition. It should be zeros > k. Also, ensure you update maxLen after the shrink loop is done to ensure the window is valid.

← Previous QuestionMinimum Window Substring
Next Question →Fruit Into Baskets