157. Flip K Zeros
A row of lamps is described by the array bits, where 1 means a lamp is on and 0 means it is off. An electrician may flip at most k of the lamps that are off, turning them on. Lamps that are already on stay on.
After the flips, the electrician looks for the longest unbroken run of lamps that are all on. Return the maximum length of such a run that can be achieved by choosing which at most k off lamps to flip. If k is larger than the number of off lamps, simply flip all of them. The array is left untouched; only the best run length is wanted.
Example 1
- Input:
- bits = [1,0,1,1,0,0,1], k = 1
- Output:
- 4
- Explanation:
Flipping the zero at index 1 turns [1,0,1,1] into four lit lamps in a row. Any window containing two zeros would need two flips, so 4 is the best.
Example 2
- Input:
- bits = [0,0,0], k = 5
- Output:
- 3
- Explanation:
There are only three zeros and k allows five flips, so all three can be flipped and the run has length 3.
Example 3
- Input:
- bits = [1,1,0,1], k = 0
- Output:
- 2
- Explanation:
No flips are allowed, so the best run is the two leading ones, giving 2.
Constraints
1 ≤ bits.length ≤ 105
bits[i] is 0 or 1
0 ≤ k ≤ 105
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 1,200 msC++ 300 msJava 600 msJavaScript 600 msTypeScript 600 ms
Expected complexity
- Time
- O(n)
- Space
- O(1)