Maximum Consecutive 1s
Problem Statement
Leetcode: Maximum Consecutive III
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]
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]
Solution
Approach: Sliding Window Technique
class Solution {
public:
int longestOnes(vector<int>& nums, int k) {
int n = nums.size();
int l = 0, r = 0, zeroes = 0;
int result = 0;
while (r < n) {
if (nums[r] == 0) {
zeroes++;
}
while (l < r && zeroes > k) {
if (nums[l] == 0) {
zeroes--;
}
l++;
}
if (zeroes <= k) { // if nums[l] == 0
result = max(result, r - l + 1);
}
r++;
}
return result;
}
};
