Max Consecutive Ones III
The key idea
Find the longest subarray that contains at most k zeros. Slide a window: expand the right edge always, and shrink the left edge only when the window holds more than k zeros. The largest window width ever seen is the answer.
Problem
Given a binary array nums and an integer k, return the maximum number of consecutive 1s in the array if you can flip at most k 0s.
Constraints
- 1 <= nums.length <= 10^5
- nums[i] is either 0 or 1
- 0 <= k <= nums.length
Examples
Input: nums = [1,1,1,0,0,0,1,1,1,1,0], k = 2
Output: 6
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
Complexity
Time: O(n) Space: O(1)
See the full solution
- ✓Full worked approach
- ✓Reference code in 5 languages
- ✓Problem-solving tips
- ✓Step-by-step animated visualization
More Sliding Window problems
- Find All Anagrams in a StringMEDIUM
- Longest Continuous Increasing SubsequenceEASY
- Longest Repeating Character ReplacementMEDIUM
- Longest Subarray of 1's After Deleting One ElementMEDIUM
- Longest Substring Without Repeating CharactersMEDIUM
- Maximum Average Subarray IEASY
- Maximum Number of Vowels in a Substring of Given LengthMEDIUM
- Minimum Size Subarray SumMEDIUM
- Minimum Window SubstringHARD
- Permutation in StringMEDIUM
- Sliding Window MaximumHARD
- Substring with Concatenation of All WordsHARD