LeetCode 75 - 1004. Max Consecutive Ones III

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.

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

Solutions

The approach for this problem is to use a sliding window, then look for the longest subarray that is 1 in length. Also, consider that when there are 0s, they can be flipped to 1s, which means that if the number of 0s is within k, they can be counted in the longest subarray of 1s.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    int longestOnes(vector<int>& nums, int k) {
        int max = {};
        int left{};
        int num{};
        for (int right = 0; right < nums.size(); ++right) {
            // When the current position is 0, record the number of 0s.
            if (nums[right] == 0) {
                num++;
            }
            // When the number of 0s exceeds k, move the left position, 
            // and at the same time determine if the current position is 0; 
            // if so, subtract one.
            if (num > k) {
                if (nums[left++] == 0)
                    num--;
            }
            // `right - left + 1` is the length of the longest sequence of 1s (including k zeros).
            max = std::max(max, right - left + 1);
        }
        return max;
    }
};