Given a binary array nums (only 0s and 1s) and an integer k, you may flip at most k zeros into ones. Return the length of the longest run of consecutive 1s you can get.
Example 1
Input: nums = [1,1,1,0,0,0,1,1,1,1,0], k = 2
Output: 6
Flip the zeros at index 5 and 10; then indices 5 to 10 are all 1s.
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
Flipping the zeros at indices 4, 5 and 9 gives ten 1s from index 2 to 11.
Constraints
- 1 <= nums.length <= 10^5
- `nums[i]` is 0 or 1
- 0 <= k <= nums.length
Hints
Frequently asked at: Meta, Amazon, Microsoft, PhonePe
Give it a real try first. Even 15 minutes of struggle makes the solution stick far better.
Intuition
Trying every subarray and counting its zeros is O(n^2). Notice that flipping is just a story: the real question is the longest subarray with at most k zeros. That is a classic sliding window. Extend right, counting zeros. When there are more than k, advance left (uncounting zeros as they leave) until the window is valid again. Each index enters and leaves once.
Algorithm
- Set
left = 0,zeros = 0,best = 0. - For each
right, ifnums[right] == 0increasezeros. - While
zeros > k: ifnums[left] == 0decreasezeros; moveleftright. - Update
best = max(best, right - left + 1)and return it at the end.
Time:
O(n)Space: O(1)Interview tip: The same template with
k = 1 solves Longest Subarray of 1s After Deleting One Element (subtract one at the end). Interviewers often chain these variants together.class Solution: def longestOnes(self, nums: List[int], k: int) -> int: left = zeros = best = 0 for right, x in enumerate(nums): if x == 0: zeros += 1 while zeros > k: # too many zeros: shrink from the left if nums[left] == 0: zeros -= 1 left += 1 best = max(best, right - left + 1) return bestCtrl + Enter runs the examples