awelgorithms

At most k zeros in the window

Updated

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.

What to focus on

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

k=1 grow

a = [1, 0, 0, 1, 9], k=1
  1. R=0 [1] zeros 0
  2. R=1 [1,0] zeros 1 len 2

Result: valid length 2

k=1 shrink

a = [1, 0, 0, 1, 9], k=1, L=0 R=2
  1. [1,0,0] zeros 2>1
  2. drop 1 zeros still 2
  3. drop 0 zeros 1, L=2

Result: [0] zeros 1

best after

a = [1, 0, 0, 1, 9], k=1, L=2
  1. R=3 [0,1] zeros 1
  2. R=4 [0,1,9] zeros 1 len 3

Result: best length 3

Try it

Write 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.

a is nonempty. Values are integers. k ≥ 0. a contains at least one valid window with zeros ≤ k.

practise it with Awel find your weak spots: free skill check

LeetCode problems that use this skill