 Coder's Cat

## LeetCode: Max Consecutive Ones III

2020-11-19

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 sub-array to meet the required property.

The time complexity is: `O(N^3)`.

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 `[1~4]`, `[1~3]` etc.

An simpler solution is called two-pointers approach.

We define two variables called`l` and `r` to store the left-index and right-index 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)`

### Python

Preparing for an interview? Check out this!

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