1004. Max Consecutive Ones III

Posted on Edited on In

1004. Max Consecutive Ones III

Description

Difficulty: Medium

Related Topics: Array, Binary Search, Sliding Window, Prefix Sum

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:

1
2
3
4
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:

1
2
3
4
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

Hints/Notes

Solution

Language: C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int longestOnes(vector<int>& nums, int k) {
        int left = 0, right = 0, res = 0, count = 0;
        while (right < nums.size()) {
            count += nums[right] ^ 1;
            while (left <= right && count > k) {
                count -= nums[left] ^ 1;
                left++;
            }
            res = max(res, right - left + 1);
            right++;
        }
        return res;
    }
};