Skip to content

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:

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

Solutions

Solution 1: Sliding Window

Thinking

Checking every subarray for its number of zeros is \(O(n^2)\), which fails for \(n\le 10^5\). Flipping at most \(k\) zeros to maximize consecutive ones is the same as the longest window that contains at most \(k\) zeros.

When the right end advances and the zero count exceeds \(k\), the left end must advance to restore feasibility. Only the maximum length is required, so the window is allowed to grow monotonically: the left end moves at most one step per iteration.

We keep \(l\) and \(\textit{cnt}\) for the current window. After the right end visits every index, \(n-l\) is the length of the longest feasible window.

We can iterate through the array, using a variable \(\textit{cnt}\) to record the current number of 0s in the window. When \(\textit{cnt} > k\), we move the left boundary of the window to the right by one position.

After the iteration ends, the length of the window is the maximum number of consecutive 1s.

Note that in the process above, we do not need to loop to move the left boundary of the window to the right. Instead, we directly move the left boundary to the right by one position. This is because the problem asks for the maximum number of consecutive 1s, so the length of the window will only increase, not decrease. Therefore, we do not need to loop to move the left boundary to the right.

The time complexity is \(O(n)\), where \(n\) is the length of the array. The space complexity is \(O(1)\).

Similar problems:

1
2
3
4
5
6
7
8
9
class Solution:
    def longestOnes(self, nums: List[int], k: int) -> int:
        l = cnt = 0
        for x in nums:
            cnt += x ^ 1
            if cnt > k:
                cnt -= nums[l] ^ 1
                l += 1
        return len(nums) - l

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
class Solution {
    public int longestOnes(int[] nums, int k) {
        int l = 0, cnt = 0;
        for (int x : nums) {
            cnt += x ^ 1;
            if (cnt > k) {
                cnt -= nums[l++] ^ 1;
            }
        }
        return nums.length - l;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
class Solution {
public:
    int longestOnes(vector<int>& nums, int k) {
        int l = 0, cnt = 0;
        for (int x : nums) {
            cnt += x ^ 1;
            if (cnt > k) {
                cnt -= nums[l++] ^ 1;
            }
        }
        return nums.size() - l;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
func longestOnes(nums []int, k int) int {
    l, cnt := 0, 0
    for _, x := range nums {
        cnt += x ^ 1
        if cnt > k {
            cnt -= nums[l] ^ 1
            l++
        }
    }
    return len(nums) - l
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
function longestOnes(nums: number[], k: number): number {
    let [l, cnt] = [0, 0];
    for (const x of nums) {
        cnt += x ^ 1;
        if (cnt > k) {
            cnt -= nums[l++] ^ 1;
        }
    }
    return nums.length - l;
}

Comments