1004. Max Consecutive Ones III

Problem Statement

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.

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.

Constraints:

• 1 <= nums.length <= 105

• nums[i] is either 0 or 1.

• 0 <= k <= nums.length

Intuition

Approach:

Maintain a variable zero_count , That keeps track of zeros in the window

Links

https://leetcode.com/problems/max-consecutive-ones-iii/description/

Video Links

Approach 1:

C++

class Solution {
public:
    int longestOnes(vector<int>& nums, int k) {
        int low=0, high=0;
        int ans=0;
        int zero_count=0;

        while(high<nums.size()){
            if(nums[high] == 0){
                zero_count++;
            }

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

                low++;
            }

            ans = max(ans, high-low+1);
            high++;
        }

        return ans;
    }
};

Approach 2:

C++

Approach 3:

C++

Approach 4:

C++

Similar Problems