Sliding Window Longest or shortest window
171. Max Consecutive Ones III
You are given an array nums in which every element is 0 or 1, and an integer k. You may flip at most
k of the 0s, which turns each of them into a 1. Return the length of the longest run of 1s you can make.
A run of 1s is a block of 1s that sit next to each other, with no 0 between them. You may flip fewer than
k zeros, or none at all.
Example 1
Input: nums = [1, 0, 1, 1, 0, 0, 1, 1, 1, 0, 1], k = 2
7Explanation: Flip the 0s at indexes 4 and 5. Then the elements from index 2 to index 8 are all 1s, a run of 7. Flipping the first two 0s, at indexes 1 and 4, gives a run of only 5.
Example 2
Input: nums = [1, 1, 0, 1, 1, 1, 0, 0, 1], k = 0
3Explanation: With no flips the array stays as it is. Its longest run of 1s is the three 1s from index 3 to index 5.
Example 3
Input: nums = [0, 0, 0, 1, 0], k = 4
5Explanation: The array holds four 0s and you may flip all four, so the whole array becomes one run of 5.
Check your understanding
Work out the answer for this input before you write any code.
Constraints
1 ≤ nums.length ≤ 105nums[i]is0or10 ≤ k ≤ nums.length
Clarifying questions
What you would ask an interviewer before writing any code.