All problems

Max Consecutive Ones III

Medium · sliding window

A list nums holds only the numbers 0 and 1. You are also given a whole number k.

You may change at most k of the zeros into ones. After you have chosen which zeros to change, look at the longest block of consecutive ones in the list. Return the greatest length that block can have, over all the ways you can choose.

You do not have to use all k changes. If nums has no ones and k is 0, the answer is 0.

Examples

Example 1

Input: nums = [1, 0, 1, 1, 0, 1, 0, 0, 1], k = 1

Output: 4

Changing the zero at position 4 joins the ones around it into 1, 1, 1, 1, which is 4 in a row. No single change gives 5.

Example 2

Input: nums = [0, 0, 0, 1], k = 2

Output: 3

Change the two zeros just before the 1 to get three ones in a row.

Example 3

Input: nums = [1, 1, 0, 1], k = 0

Output: 2

With no changes allowed, the best block is the two ones at the start.

Constraints

• 1 <= len(nums) <= 10^5
• nums[i] is 0 or 1
• 0 <= k <= len(nums)