**Difficulty:** Medium, **Asked-in:** Amazon, VMware

**Key takeaway:** This is one of the best problems to understand the idea of the sliding window technique. Using this approach, we can solve several interview problems efficiently in O(n) time and O(1) space.

You are given an array of **1**s and **0**s and you are given an integer **k** which signifies the number of flips allowed. Write a program to return the count of the maximum number of consecutive 1's in the array if you can flip at most k 0's.

Input: X[]= [1, 0, 0, 1, 1, 0, 1, 0, 1, 1, 1], k = 2, Output: 8

**Explanation:** We are allowed to flip a maximum of 2 zeroes. If we flip X[5] and X[7], we get 8 consecutive 1’s which is the maximum possible under given constraints.

Input: X[] = [1, 1, 0, 1, 0, 1, 0, 0, 1], k = 1, Output: 4

**Explanation:** We are allowed to flip a maximum of 1 zero. If we flip X[2], we get 4 consecutive 1's which is the maximum possible under given constraints.

- A brute force solution using nested loops
- An efficient solution using a sliding window technique

**Solution Idea**

A brute force solution is to consider every subarray by running two nested loops. For every subarray, we count the number of zeroes in it and return the maximum size subarray with k or fewer zeroes. **(Think!)**

**Solution Pseudocode**

```
int maxConsecutiveOne(int X[], int n, int k)
{
int leftEnd, rightEnd
int maxOneCount = 0
for(int i = 0; i < n; i = i + 1)
{
int countZeros = 0
for(int j = i; j < n; j = j + 1)
{
if(X[j] == 0)
{
countZeros = countZeros + 1
if(countZeros > k)
break
}
}
j = j - 1
if(maxOneCount < (j - i))
maxOneCount = j - i + 1
}
return maxOneCount
}
```

**Time and space complexity analysis**

In the worst case, we need to check every small subarray. For this, we are running two nested loops in the solution where for every value of i, j is going from i to n-1. Total no of loop count = n + n -1 + n-2 …+ 1 = n(n-1)/2 = O(n²)

Space Complexity = O(1)

**Solution Idea**

The critical question is: can we improve the solution further and solve this problem using a single traversal array? Is there some insight into the problem which could help us to build a better solution? Let's think!

There are only 0's and 1's in the array. So there would be two scenarios:

- If the number of 0's > k: then we need to track the maximum subarray size with k number of zeroes.
- If the number of 0's < k: then the output will be the size of the array. Think!

So the idea using the sliding window would be to track each window with k number of 0's and find the maximum size of such window. How do we do this? Let's think! The idea is to scan the array using a loop and count the 0's in each window:

- When 0's count is less than k, we keep moving forward in the current window by counting 0's and tracking the maximum number of 1 count using a variable.
- When 0's count is greater than k, we slide the left end of the current window by one forward. But before doing this, we need to update the zero count of the new window by checking that the left end of the previous window is 0 or 1. If it is 0, then we decrement the zero count by 1.
- We again continue step 1 for the current window by counting 0's and tracking the maximum number of 1 count.

**Solution Steps**

- We initialize two variables
**zeroCount**and**maxOneCount**to track the zero count in the current window and max possible one count at the current point. zeroCount = 0 and maxOneCount = 0. - We also initialize a pointer
**l = 0**to track the left end of the current window and run a loop from**r = 0 to n - 1**to access each window. Note: here, loop pointer r will track the right end of the current window. -
- When X[r] = 0, we increment the zeroCount by 1.
- When zeroCount is greater than k, we slide the current window by incrementing the left pointer l. But before this, we check the left end of the previous window: if(X[l] == 0), then we update the zero count of the current window by decrementing the zeroCount.
- At each step of the iteration, we keep tracking the max possible 1 count i.e. maxOneCount = max(maxOneCount, r - l + 1)

- By the end of the loop, we return the value stored in the variable maxOneCount.

**Solution Pseudocode**

```
int maxConsecutiveOne(int X[], int n, int k)
{
int zeroCount = 0, l = 0
int maxOneCount = 0
for (int r = 0 ; r < n; r = r + 1)
{
if(X[r] == 0)
zeroCount = zeroCount + 1
if(zeroCount > k)
{
if(X[l] == 0)
zeroCount = zeroCount - 1
l = l + 1
}
maxOneCount = max(maxOneCount, r - l + 1)
}
return maxOneCount
}
```

**Time and space complexity analysis**

In the above code, we are running a single loop and doing a constant number of operations at each iteration. So time complexity = n*O(1) = O(n). We are only using a constant number of extra variables, so space complexity = O(1)

- How do we modify the above code when we need to return the indices of the maximum continuous series of 1s in order?
- There could be multiple possible solutions. How can we modify the above code to return the sequence which has the minimum start index?
- Can we think to solve this problem using some other approaches?
- What would be the worst and best scenario of the above approaches?
- Do both approaches handles scenario when the number of 0's are less than k in the input?

- Count Number of Nice Subarrays
- Replace the Substring for Balanced String
- Max Consecutive Ones
- Binary Subarrays With Sum
- Subarrays with K Different Integers
- Fruit Into Baskets
- Shortest Subarray with Sum at Least K
- Minimum Size Subarray Sum

**Enjoy learning, Enjoy coding!**

Get well-designed application and interview centirc content on ds-algorithms, machine learning, system design and oops. Content will be delivered weekly.