1004. Max Consecutive Ones III

Problem Description

You are given a binary array nums and an integer k. You can flip at most k values from 0 to 1. Your task is to return the length of the longest contiguous subarray that contains only 1s after flipping at most k zeroes.

Constraints

• 1 <= nums.length <= 10^5

• nums[i] is either 0 or 1

• 0 <= k <= nums.length

Intuition

The problem revolves around forming the longest subarray of 1s by flipping at most k zeroes to 1s. This naturally lends itself to a sliding window approach, where we expand and contract a window based on the number of zeroes inside it. The key observation is that as long as the count of 0s inside the window is less than or equal to k, the window is valid. When it exceeds k, we shrink the window from the left.

Solution Approach

We initialize two pointers, left and right, to mark the window’s boundaries. As we move right through the array:

• Count how many zeros are in the current window.

• If the number of 0s exceeds k, move the left pointer to the right until the window has k or fewer 0s.

• Track the maximum window length encountered.

This approach ensures we check all valid subarrays without recomputation, giving an optimal O(n) solution.

Example Walkthrough

Example 1:

Input: nums = [1,1,1,0,0,0,1,1,1,1,0], k = 2
Flips: Flip zeroes at indices 5 and 10.
Longest subarray: [1,1,1,0,0,1,1,1,1,1,1] (length = 6).
Note: We only flip two zeros (as k = 2), so the window [0,5] or [5,10] is the best choice.

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
Flipping the zeroes at indices 4, 5, and 9 yields a segment of 10 consecutive 1s.
Output: 10.

Solution Implementation

🔹 Brute Force Solution

Try all subarrays, count zeros, and check if they are within the allowed k.
Time Complexity: O(n²), Space Complexity: O(1) — Inefficient for large inputs.

public class Solution {
    public int longestOnes(int[] nums, int k) {
        int n = nums.length;
        int maxLen = 0;

        for (int i = 0; i < n; i++) {
            int zeros = 0;
            for (int j = i; j < n; j++) {
                if (nums[j] == 0) zeros++;
                if (zeros > k) break;
                maxLen = Math.max(maxLen, j - i + 1);
            }
        }
        return maxLen;
    }
}

int longestOnes(vector<int>& nums, int k) {
    int n = nums.size();
    int maxLen = 0;

    for (int i = 0; i < n; i++) {
        int zeros = 0;
        for (int j = i; j < n; j++) {
            if (nums[j] == 0) zeros++;
            if (zeros > k) break;
            maxLen = max(maxLen, j - i + 1);
        }
    }
    return maxLen;
}

def longestOnes(nums, k):
    n = len(nums)
    max_len = 0
    for i in range(n):
        zeros = 0
        for j in range(i, n):
            if nums[j] == 0:
                zeros += 1
            if zeros > k:
                break
            max_len = max(max_len, j - i + 1)
    return max_len

var longestOnes = function(nums, k) {
    let maxLen = 0;
    for (let i = 0; i < nums.length; i++) {
        let zeros = 0;
        for (let j = i; j < nums.length; j++) {
            if (nums[j] === 0) zeros++;
            if (zeros > k) break;
            maxLen = Math.max(maxLen, j - i + 1);
        }
    }
    return maxLen;
};

Optimal Solution (Sliding Window)

Efficiently manage a window with at most k zeroes.

public int longestOnes(int[] nums, int k) {
    int left = 0, zeros = 0, maxLen = 0;
    for (int right = 0; right < nums.length; right++) {
        if (nums[right] == 0) zeros++;
        while (zeros > k) {
            if (nums[left++] == 0) zeros--;
        }
        maxLen = Math.max(maxLen, right - left + 1);
    }
    return maxLen;
}

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

def longestOnes(nums, k):
    left = 0
    zeros = 0
    max_len = 0
    for right in range(len(nums)):
        if nums[right] == 0:
            zeros += 1
        while zeros > k:
            if nums[left] == 0:
                zeros -= 1
            left += 1
        max_len = max(max_len, right - left + 1)
    return max_len

var longestOnes = function(nums, k) {
    let left = 0, zeros = 0, maxLen = 0;
    for (let right = 0; right < nums.length; right++) {
        if (nums[right] === 0) zeros++;
        while (zeros > k) {
            if (nums[left++] === 0) zeros--;
        }
        maxLen = Math.max(maxLen, right - left + 1);
    }
    return maxLen;
};

Time and Space Complexity

🔸 Brute Force:

• Time Complexity: O(n²)

• Space Complexity: O(1)

🔸 Optimal (Sliding Window):

• Time Complexity: O(n) — each element is processed at most twice (once by right, once by left)

• Space Complexity: O(1) — uses a few pointers and counters