At most k zeros in the window07.03
Count zeros in a[L..R]. Expand R (zeros += 1 if a[R]==0). While zeros > k, drop a[L] and decrement if it was 0. Valid windows have zeros ≤ k.
Non-zeros never raise the counter. This is longest ones-with-flips when the array is 0/1. Here 9 is just another non-zero.
worked examples
Same skill, three traces. Read all three before you try it.
01k=1 grow - given
a = [1, 0, 0, 1, 9],k=1- walk
R=0[1]zeros0R=1[1,0]zeros1len2- result
- valid length
2
02k=1 shrink - given
a = [1, 0, 0, 1, 9],k=1,L=0R=2- walk
[1,0,0]zeros2>1drop
1zeros still2drop
0zeros1,L=2- result
[0]zeros1
03best after - given
a = [1, 0, 0, 1, 9],k=1,L=2- walk
R=3[0,1]zeros1R=4[0,1,9]zeros1len3- result
- best length
3
Write
Return the best length, which must be
On
longestAtMostKZeros(a, k).a is an array of integers. k is the zeros budget. L is the left index. R is the right index. The window includes a[L..R]. Valid means zeros ≤ k.Return the best length, which must be
3.On
[1, 0, 0, 1, 9] with k=1.constraintsa is nonempty. Values are integers. k ≥ 0. a contains at least one valid window with zeros ≤ k.
- Max Consecutive Ones III0/3 skills ready · sliding window · mediumopen
- Max Consecutive Ones III0/3 skills ready · sliding window · mediumopen
Every Check with Awel is frozen here. Open one to read the code or load it back into the editor.