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 Solve

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.

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.

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;
}

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²) time.

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;
}

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

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.

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;
}

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!