Programmers Army

Sliding Window Approach

In the sliding window approach, we avoid doing redundant work. For example, if we need to find the sum of each subarray of size k we can find the sum of the next subarray using the previous values. If our array is [ 3 , 7 , -5 , 10 , 2 , 4 , 8 , -3 , 11 ]. We need to find the sum of each 4 – length subarray. Then we do as follows:-

The sum of the first subarray is 3 + 7 + -5 + 10 = 15.

Then to find the sum of the subarray of [ 7 , -5 , 10 , 2 ] we see that 7 , -5 and 10 remain common so we do not need to add those values again. Instead we see that only 3 gets subtracted and 2 gets added. Therefore the next sum is 15 - 3 + 2 = 12. This the essence of the sliding window approach.

Consider the following problem (taken from Leetcode # 1052 = Grumpy Bookstore Owner):

Q - There is a bookstore owner who is grumpy on some minutes and not grumpy on other times. We are given an array of n integers called grumpy where grumpy[i] = 1 if the owner is grumpy on minute i and grumpy[i] = 0 otherwise. Additionally, we are also given another array of n integers called customers where customers[i] tells us the number of customers entering the store on minute i. We can change at most X consecutive values of the grumpy array and we need to determine the maximum number of customers that can be satisfied throughout the day.

Hints:

· First observation is that the bookstore owner will receive customers on all day on which he is not grumpy. Thus, we can store that as our initial answer.

· Now for each subarray of size X we can change all grumpy values which are 1 to 0 and in this way, we can satisfy all customers in that interval of size X.

· The Brute Force should be hopefully clear now since we just sum all X length subarrays from the customers array (be careful of not double counting the ones from step 1.) and take the maximum of them.

· However, this will be very inefficient, so is there any optimization possible?

· Which customer values are we including and which are being excluded when we go from one interval to the next?

· We need to find an efficient way to go from one interval to the next by using our previous results.

· Try to write down, one a piece of paper, each customer value included and each one excluded when moving from one interval to the next.

Approach 1 (Brute Force):

· Initially we sum all the values in the customers array with grumpy = 0 in the corresponding grumpy array and then we consider each subarray (or window) of size X.

· We add all the values in the current window of size X with grumpy being 1 in the grumpy array (this is because we have changed all the grumpy values from 1 to 0 in this window)

· We keep track of the maximum at each step and return it.

· Although this might get accepted on Leetcode the complexity is O(n*k) so you can expect it to fail on stricter testcases.

have a look at below code:

Time Complexity: O(n*k)

Space Complexity: O (1) excluding input arrays

Approach 2 (Sliding Window):

· You should have observed by now that we when we are transitioning from one state to another the only information which is changing is one value which we are excluding and one new value which we are including (this is the essence of the sliding algorithm where we can efficiently update val in the above code instead of recomputing all the intermediate values )

· Thus, we only need to subtract the customer size from the previous window if the owner was grumpy on that minute.

· We also need to add the customer size from the current minute if the owner is grumpy on this minute.

· Now the algorithm should be clear. The code below will further clarify your doubts and this code is actually shorter to write than the brute force which might be the case in a lot of sliding window questions since we only need to change two values ( exclude the values from the previous window and include the value from the current window ) instead of recomputing everything.