Longest run of ones with k flips
We'll cover the following
Given 0s and 1s and a number k, find the longest run of 1s you can make by flipping at most k zeros.
Watch it run
Press Play or Step to walk through the example, or change the input and press Run. Each frame says what the algorithm does and why.
L/R00
01
12
03
04
05
06
07
08
19
010
011
012
013
114
115
016
017
1 zero in the window, within the limit. Length 1.
zeros 1 · best 1
1 / 33
The idea
Complexity
| Time | Space | Why |
|---|---|---|
O(n) | O(1) | Two forward-only pointers and a zero counter. |
In Python
def longest_ones(nums, k):
l = zeros = best = 0
for r, x in enumerate(nums):
zeros += (x == 0)
while zeros > k:
zeros -= (nums[l] == 0); l += 1
best = max(best, r - l + 1)
return bestSummary: say it in the interview
- Rephrase it: find the longest window containing at most k zeros. Count the zeros inside and shrink L when the count goes over k.
- Time O(n), space O(1). Two forward-only pointers and a zero counter.