Given an array A of 0s and 1s, we may change up to K values from 0 to 1.
Return the length of the longest (contiguous) subarray that contains only 1s.
The naïve solution is enumerate all the range pairs of array, check whether we have a consecutive sub-array to meet the required property.
The time complexity is:
Of course, this is a very slow solution, and we will get time-limit exceed.
Solution with approach of two-pointers
In the previous solution, there are duplicated computation. For example,
[1~5] will contains the computation of
An simpler solution is called two-pointers approach.
We define two variables called
r to store the left-index and right-index of a window. What we need to do is keep the required property and move
r according to current status.
We can use a
count to store the number of 0s in the window. When the number of 0s in the window is greater than K, we need to shrink the window. In every iteration, we compare the window size with the final result to determine whether to update the result.
Preparing for an interview? Check out this!