1004. Max Consecutive Ones III

Description

The problem involves finding the maximum number of consecutive 1s in a binary array by flipping at most k 0s to 1s. This is a common sliding window problem that deals with managing a subarray of consecutive elements under certain constraints.

Intuition

The intuition behind the solution is to maintain a sliding window that represents a valid sequence where the number of zeros does not exceed k. As you expand the window by adding new elements, you check whether the sequence is still valid. If the sequence becomes invalid, the window is contracted from the left to restore validity. Throughout this process, the maximum length of valid sequences is tracked.

Approach

1. Initialize two pointers, l and r, representing the left and right bounds of the sliding window.
2. Traverse through the array with the right pointer r, adding each element to the current window.
3. Decrease k when a 0 is encountered in the window.
4. If k becomes negative (indicating more than k 0s in the window), increment the left pointer l to reduce the size of the window and restore k to a non-negative value.
5. Track the maximum length of the window throughout the process.
6. Return the maximum length found.

Complexity

Time Complexity:

O(n), where n is the number of elements in the array. Each element is processed at most twice, once by the right pointer and once by the left pointer.

Space Complexity:

O(1), as the algorithm only uses a few extra variables to keep track of the pointers and counts.

Code

C++

class Solution {
public:
    int longestOnes(std::vector& nums, int k) {
        int l = 0, max_num = 0;

        for (int r = 0; r < nums.size(); r++) {
            k -= 1 - nums[r];

            if (k < 0) {
                k += 1 - nums[l];
                l++;
            } else {
                max_num = std::max(max_num, r - l + 1);
            }
        }
        return max_num;
    }
};

Python

class Solution:
    def longestOnes(self, nums: List[int], k: int) -> int:
        l = 0
        max_num = 0

        for r in range(len(nums)):
            k -= 1 - nums[r]

            if k < 0:
                k += 1 - nums[l]
                l += 1
            else:
                max_num = max(max_num, r - l + 1)

        return max_num

Java

class Solution {
    public int longestOnes(int[] nums, int k) {
        int l = 0, max_num = 0;

        for (int r = 0; r < nums.length; r++) {
            k -= 1 - nums[r];

            if (k < 0) {
                k += 1 - nums[l];
                l++;
            } else {
                max_num = Math.max(max_num, r - l + 1);
            }
        }

        return max_num;
    }
}

JavaScript

var longestOnes = function (nums, k) {
    let l = max_num = 0

    for (let r = 0; r < nums.length; r++) {
        k -= 1 - nums[r]

        if (k < 0) {
            k += 1 - nums[l]
            l++
        } else {
            max_num = Math.max(max_num, r - l + 1)
        }
        console.log(l, r)
    }

    return max_num
};