1004. Max Consecutive Ones III

1. Description

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.

2. Example

Example 1

Input: nums = [1,1,1,0,0,0,1,1,1,1,0], k = 2
Output: 6
Explanation: [1,1,1,0,0,1,1,1,1,1,1]
Bolded numbers were flipped from 0 to 1. The longest subarray is underlined.

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
Explanation: [0,0,1,1,1,1,1,1,1,1,1,1,0,0,0,1,1,1,1]
Bolded numbers were flipped from 0 to 1. The longest subarray is underlined.

3. Constraints

• 1 <= nums.length <= 10$^5$
• nums[i] is either 0 or 1.
• 0 <= k <= nums.length

4. Solutions

Sliding Window

n = nums.size()
Time complexity: O(n)
Space complexity: O(1)

class Solution {
public:
    int longestOnes(const vector<int> &nums, int k) {
        const int n = nums.size();
        int left = 0, zero_count = 0, max_length = 0;
        for (int right = 0; right < n; ++right) {
            if (nums[right] == 0) {
                ++zero_count;
            }

            while (zero_count > k) {
                if (nums[left] == 0) {
                    --zero_count;
                }

                ++left;
            }

            max_length = max(max_length, right - left + 1);
        }

        return max_length;
    }
};