# Sliding Window - 2

In the last article, you learnt about sliding window of fixed size. Now let's get our hands dirty and learn about sliding window of **variable size**.

Let's solve a problem to understand the concept in detail.

## Maximum Consecutive Ones III

Given a binary array *nums *and an integer *k,* return the maximum number of consecutive 1's in the array if you can flip at most *k* 0s to 1s.

### What is a Binary Array?

Every element of a binary array is equal to either 0 or 1.

Let's take an example to understand the above problem more clearly.

**Input: **nums = [1,1,1,0,0,0,1,1,1,1,0], k = 2**Output: **6**Explanation: **[1,1,1,0,0,** 1**,

__1__,

__1__,

__1__,

__1__,

**]**

__1__Bolded numbers were flipped from 0 to 1. The longest subarray is underlined.

### Let's get solving!

It's time to put on your problem solving hats and start by thinking of a brute-force solution.

One greedy observation is: We will try to flip all the 0's in a particular subarray such that its length is maximised. In other words, **we have to find longest subarray such that number of 0's in it are less than or equal to K.**

#### Why?

We can flip all those 0's and we will have a subarray with all 1's!

Hmm.... subarrays. Rings a bell? Yes! we already know how to iterate over all subarrays of an array.

So we just need to find every subarray, and check if the number of 0s in that subarray is less than or equal to K or not. If yes, the length of this subarray could be a possible answer & we can update our answer accordingly.

## Implementation

```
int longestOnes(vector<int> &nums, int k) {
int n = nums.size();
//answer will be atleast zero
int ans = 0;
for(int st=0 ; st<n ; st++) {
for(int en=st ; en<n ; en++) {
int curr_zeros = 0;
for(int i=st ; i<=en ; i++) {
if(nums[i]==0) curr_zeros++;
}
if(curr_zeros<=k) ans = max(ans, en-st+1);
}
}
return ans;
}
```

#### Time & Space Complexity

**Space Complexity: O(1)**

Because we don't require any additional space other than * ans* variable.

**Time Complexity: O(n**^{3}**)**

We require two nested for loops to find all the subarray (n^{2}) and we need another nested for loop to iterate over the subarray (n)

O(n^{2} x n) = O(n^{3})

### Observing Redundancy

Now, let's get fancy. ** **We can think of a subarray as a **window, **so in this article, we will use the words 'window' and 'subarray' interchangeably.

Try to think about something redundant which we were doing in the above approach which is not required.

If we already have more than k 0's in a subarray, is it wise to expand the window? No! expanding that window will only give us subarrays which will have more than k 0's.

We can go to every index of the array and expand the window till we encounter (k+1)th zero. Now we cannot expand the window further because it will result in more than k zeros in the window. Do this for every index and we get an algorithm which runs in **O(n ^{2}) **time.

## Implementation

```
int longestOnes(vector<int>& nums, int k) {
int n = nums.size();
int ans = 0;
for(int st=0 ; st<n ; st++) {
int en = st;
int curr_zeros = 0;
for(; en<n ; en++) {
if(nums[en]==0) curr_zeros++;
if(curr_zeros>k) break;
}
ans = max(ans, en-st);
}
return ans;
}
```

#### Time and Space complexity

**Space Complexity: O(1)**

We just need one variable * ans* to store the final answer

**Time Complexity: O(n**^{2}**)**

For every index, the inner for loop can run till (n-1) index in the worst case.

Adding up the iterations: n + (n-1) + (n-2) + .... + (1) = n*(n+1)/2

O(n*(n+1)/2) ~ O(n^{2})

### More Redundancy!

Great going! Can we observe some more redundancy in the above algorithm?

When we found (k+1)th 0 in the above algorithm, we entirely got rid of the window and started expanding from next index with window size 0. Is it necessary?

Instead, we can contract the window till the number of 0's the window get back to being less than or equal to K, and then we get back to expanding again. So the entire algorithm will be a series of expansions and contractions based on the number of 0's in the window. Also meanwhile, we keep updating our answer whenever we have a window with number of zeroes less than or equal to K.

Let *curr_zeros* denote the number of 0's in the current window:

If curr_zeros <= k -> expand window & update answer

If curr_zeros > k -> contract window

#### How do we maintain our window in the code?

With two pointers. One for the start of the window (call it * st*), and one for the end of the window (call it

*)*

*en*#### Why don't we name our variables *start* and *end*?

*start*

*end*

Now you may argue that why don't we name our variables * start* and

*end.***But in most of the STL containers, we have a method named as**

**Well you can!***so to have a clear distinction between variables and functions we name our variables with a unique name.*

*end(),*### Let's get Coding!

Enough of chit-chat. Let's do the real thing. Code!

Now sliding window, or in fact, any algorithm can be implemented in many ways. Even you can (and you should) have your own version of the implementation as long as it follows the same logic.

You know the logic now. Go try implementing it on your own, and come back to see my version of implementation.

## Implementation

```
int longestOnes(vector<int>& nums, int k) {
int n = nums.size();
int ans = 0;
// initialize two pointers
int st=0, en=0;
//variable to store zeros in the window
int curr_zeros = nums[0] == 0? 1 : 0;
while(en<n) {
if(curr_zeros<=k) {
//expand
ans = max(ans, en-st+1);
en++;
if(en>=n) break;
curr_zeros += 1-nums[en];
} else {
//contract
if(nums[st]==0) {
curr_zeros--;
}
st++;
if(st>en) {
en=st;
if(en>=n) break;
curr_zeros = 1-nums[en];
}
}
}
return ans;
}
```

#### Time and space complexity

**Space Complexity:O(1)**

We just need two variables * st *and

*to maintain the endpoints of window.*

*en***Time Complexity: O(n)**

In each iteration, either * st* is incremented or

*is incremented. So thw while loops runs at most*

*en**times.*

*2n*O(2*n) ~ O(n)

### Bonus: Binary Search (Just the idea)

Okay geeks if you already know binary search, I got you covered. But if you don't know binary search, no need to worry you can come back when we learn it. And anyway, binary search solution has **slightly greater running time complexity** than our sliding window algorithm😉.

Let's define a function:

f(n) = {

**true**: if we can find a subarray of length n with <= k 0's

**false**: otherwise

}

This function is monotonic. Think about it.

And we can apply binary search on monotonic inputs.

Now I am leaving the rest as an exercise for you :) Don't stress out if you are not able to understand the binary search logic for now.

For now, Adios and Happy Learning!