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(vector<int> &nums, int k) {
        int max_ones = 0;
        for (int left = 0, right = 0, zero_count = 0; right < nums.size(); ++right) {
            zero_count += (nums[right] == 0 ? 1 : 0);
            while (zero_count > k) {
                zero_count -= (nums[left] == 0 ? 1 : 0);
                ++left;
            }

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

        return max_ones;
    }
};