2/180: Sliding Window Algorithms

So today is 2nd day of 180 days streak. And I began my day with Data Structures and gone thoroughly through the window sliding problems. Lets begin:

First of all let us find out how to identify if the problem can be solved using sliding window algorithm. You would be given an input array and a window size K or the question can be to find out the window size. There are two types of Sliding window Algorithms. One is Fixed and the other is Variable.

Lets considers few examples questions of fixed size and variable size windows.

Fixed Size Window

Max/Min sum subarray of size K?

1st negative number in every subarray of size K?

Count occurrences of anagram?

Max of all subarray of size K?

Variable Size Window

Largest/smallest subarray with sum K?

Largest substring of K distinct characters?

Length of Largest substring with no repetitive character?

Minimum window substring.

So I am going to explain 1 question of each type and all other questions are variation of the same.

Lets begin with our first question

Max/Min sum subarray of size K?

Lets say we have input array of size 7 and the values are {2,3,2,1,6,3,-1} and we have to find subarray of size 3. That means 3 is the size of our window. By subarray it refers to continuous elements without any gap.

Lets see all the window of size 3 which can be formed from this array

1. 2 + 3 + 2 = 7
2. 3 + 2 + 1 = 6
3. 2 + 1 + 6 = 9
4. 1 + 6 + 3 = 10
5. 6 + 3 — 1 = 8

So there are total 5 subarrays and if talking about the maximum sum it is 10, we can output {1,6,3} = 10. If the question is to find minimum then minimum sum is 6 and subarray is {3,2,1} = 6

So to solve this problem what we need is start index and end index of a subarray. Lets talk about the brute force. we can start from 0th index and consider 0th as start index (i) and end index (j) both. Now increment j till we reach the size of subarray given and ultimately j will be at position 3, i.e. 2nd index. We have reached the size of subarray and while we increment we also have to calculate the sum and store it as a max value, so now we have got our first subarray, what next we can do is increment and i and make j = i, and again traverse j till size becomes equal to the size of subarray, and we can compare the sum with the previous sum, if current sum is greater than previous one we can replace and this loop will go on till (j) reaches the length of array i.e. at the end. And we can get our max sum. Now the problem with this approach is that

1. 2 + 3 + 2 = 7 at (0,1,2) index respectively
2. 3 + 2 + 1 = 6 at (1,2,3) index respectively

if you consider these two subarray, you can see there is repetition, 3+2 are getting added twice, though currently the subarray size is small so it doesn't matter, but if the subarray size is greater then it can cause longer execution time.

To solve this problem we have to maintain the window size. To do so what we can do is, we can start from the 0th index only and set it start and end index i & j respectively, now we will do the same way. will move j till we reach the size of subarray, and side by side will calculate the sum. so now we have got our first subarray, what next we can do is increment and i and j both, i.e. i++ and j++, when we do i++ and j++, our window size don’t change but we have to remove the last value from the subarray and add new value to the subarray in this way the size of window will be maintained and we will get the correct sum also and this loop will go on till (j) reaches the length of array i.e. at the end. And we can get our max/min sum.

Lets talk about the variable size window problem

Largest/smallest subarray with sum K?

In variable size of window, we are not provided with size of window and we actually have to find. Lets take an Input array of size 7 and the values are {2,3,2,1,1,1,1} and we have to find largest subarray of with sum equal to 5.

lets see all the sub arrays with sum equal to 5

1. 2+3 = 5, size of subarray = 2
2. 3+2 = 5, size of subarray = 2
3. 2 +1 +1 +1 = 5, size of subarray = 4

So the largest subarray is of of size 4 i.e. {2,1,1,1}

No here we don’t have fixed window size and we need to know the size, what we have is sum, so to approach its solution, we have to do that same way we did for fixed size subarray, but here we will increase the window size till the sum of subarray is equal to the given value, and we can store the size of subarray and in last we can print the maximum size of subarray. The only difference is we will increment the window till we get the sum. if the sum becomes greater than the given sum, at that point we can exclude the value from the start of array and can do i++, otherwise j++ till we reach the length of array.