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.
Example 1:

Naïve solution
The naïve solution is enumerate all the range pairs of array, check whether we have a consecutive subarray to meet the required property.
The time complexity is: O(N^3)
.

Of course, this is a very slow solution, and we will get timelimit exceed.
Solution with approach of twopointers
In the previous solution, there are duplicated computation. For example, [1~5]
will contains the computation of [1~4]
, [1~3]
etc.
An simpler solution is called twopointers approach.
We define two variables calledl
and r
to store the leftindex and rightindex of a window. What we need to do is keep the required property and move l
or 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.
Time complexity: O(n)
Space complexity: O(1)
Cpp

Java

Python

Join my Email List for more insights, It's Free!😋