Top and Mostly asked problems on sliding window technique

byCrazyTechie •
0

A sliding window is an algorithmic technique based on the two-pointer technique that aims to reduce the use of a nested loop to a single loop and helps in bringing the exponential complexity to linear time complexity. I welcome you to an amazing series of competitive programming with python and taking the series forward in this tutorial we will continue the Two pointer algorithm and will study and solve amazing problems on the sliding window technique.

Mostly asked sliding window coding problems in interviews

Table of Contents


Introduction to sliding window technique

A sliding window is basically a type of two-pointer technique in which we are asked to find answers under a certain length (window) based on some condition. In the article on two pointer technique, we have seen how two-pointers are used to optimize the exponential complexity to linear time and in the same way, a sliding window is a little bit more advanced version of two-pointers.

Types of Sliding window algorithm

There are two types of use cases of the sliding window technique and we will study and solve the questions in respective categories.

1) Fixed Size sliding window - As the name suggests that the size of the window will be given in the question and while approaching these types of questions the distance between two pointers is maintained.

2) Variable-size sliding window - In the variable-size sliding wind, ow the size of the window is not given and based on the certain condition we are supposed to increase or decrease the window, size, and in most of the problems we are only asked to return the minimum or maximum window size based on certain condition.

I hope that a little bit of what sliding window technique is clear to you. A better understanding will come when we will understand it with examples and solve some problems. I only request you to be on the topic and continue reading forward with full enthusiasm.

1) Maximum sum subarray of size k

Problem Statement - Given an array of N integers and an integer K., your task is to find the maximum sum subarray of size k. In simple words, you have to find all the subarray of size K and return the sum of that subarray whose sum is maximum.

Example

  • The first line contains the size of the array. 
  • the second line contains an array of elements
  • The third line contains an integer K representing the size of the window (subarray length)


🔰 Naive Approach

Every beginner now who understands the problem statement will definitely think over this solution to simply apply two loops. The first loop run from 0 till N. second (inner loop) starts from me till I+K and finds its sum and updates the answer.

💡Optimizing the maximum sum approach using the sliding window technique

Repetitive task - Implement the naive approach or solve it on paper and find where we are doing the repeat task and is there a way to overcome it. Suppose we have K as 3 and the size of the array as 7. So while finding the first subarray from 0 to 3 we add elements as the first three indexes. Again when we move to the next subarray we find the sum of elements from the 1st index to the 4th index. So elements present in the second and third positions are again involvedolve in the calculation.

Sliding Window approach - Always remember that where there occur is repetition then there is optimization. So we have already added the first, second, and third elements for the first subarray. Now what I can do is I have to only add the fourth element so I can add the fourth element and subtract the element at the first position and we have some of the second subarrays.

So we are only removing the first element and adding the last element and all the middle calculations are already done. 

Algorithm - Now let us discuss implementing the algorithmic approach.

  • We have a two-pointer as the start and end. Both initially are pointing at the first position.
  • Start the loop till the end pointer is less than the array size. Add the elements to a sum till we do not reach window size (K). window size is simply denoted as (End - start + 1).
  • As we reach equal window size we have to update the maximum sum. And remove the calculations of the first element so subtract the element at the start pointer and increase both the pointer.

💻 CODE ~ let us code it in python. you can try it in different language too.

def maxSubarraySum(arr, n, k):
    max_sum = 0 #resultant answer
    curr_sum = 0
    
    #define two pointer
    start = 0
    end = 0
    
    #start iterating till N
    while end < n:
        #initial calculations
        curr_sum = curr_sum + arr[end]
        
        #check if window size (subarray) is less then k
        if ((end - start + 1) < k):
            end += 1
            
        #if we reach window size equal to K
        elif ((end - start + 1) == k):
            #update maximum sum
            max_sum = max(max_sum, curr_sum)
            
            #remove first element of window and add next element
            curr_sum = curr_sum - arr[start]
            #slide the window forward
            start += 1
            end += 1
            
    return max_sum
    
    
arr = [1, 4, 2, 10, 2, 3, 1, 0, 20]
k = 4
n = len(arr)
print(maxSubarraySum(arr, n, k))

How to identify the problems belonging to sliding window algorithm

These is the questions that point in everyone head and are are also important to ask when I am supposed to the use sliding window algorithm.

  1. The question must be of array or string. and you are asked to find the subarray or substring.
  2. The size of the window will be given or the condition is given and the window size is asked to return as output.

😏Whenever these 2-3 criterion meets then always think of the sliding window algorithm as an approach to apply and implement the solution. Now we have a good idea of the sliding window technique so let us solve some questions on fixed size sliding window then we will move to variable size sliding window.

2) First negative Number in every window of size K

Problem statement - Given an array of N integers (positive and negative), and an integer K (window size). Your task is is to find first negative number of all the subarray of size K. If subarray did not contain any negative number then return 0 for that subarray.

Example

We are given a function that accepts array of integers, array size and an integer K which is window size.


💡Approach 

The basic approach would be brute-force that everyone must think to use two loops and using second loop iterate through required subarray and where we find negative element add it and terminate the inner loop to next subarray.

Sliding Window Identification

  • The question is of array or string (Yes)
  • We are asked subarray of substring (Yes)
  • Window size or condition of window is given of not (Window size is given)

Sliding window approach - Brute-force will not help in clearing all test cases as well as in interviews. Now we need to think off where we are doing a repetitive tasks. We will request you to use maximum sum subarray problem approach to take as a reference and try to implement the same approach on this problem statement because all sliding window questions are almost similar.

  • We can see that for N number of elements (N - K + 1 ) numbers will be there in resultant list. Now in sliding window technique we have two pointer that initially points at 0 position.
  • We need to keep track of negative numbers in ana array so we will define one empty list to store negative numbers while we iterate. The step is same as calculation of doing sum in previous problem but here we need to check for negative number so we will store negative number.
  • Till we did not reach window size we will increate end pointer.
  • As we hit window size so we need to do two step here. First is to find answer of current subarray and second is to slide the window that means to add next element and remove previous calculation to maintain window size.
  • In this as we hit window size we will get the answer of first negative from list in which we are storing negative numbers. So we want first negative so just check that if negative number list is not empty then add the first element of it to result list.
  • And to slide the window just check the first element(start pointer) is not equal to first element of negative number list. If it happen then remove this element to remove its calculations and slide the window by moving both pointer in forward direction.

💻 Code - Read the approach very carefully and I have added the comments to code to understand the approach and we request you to solve sample input with code on paper.

def firstNegativeNumber(arr, n, k):
    start = 0
    end = 0
    neg_nums = [] #to store all neg nums
    result = []  #final result
    
    #start till end pointer is less then n (Step-1)
    while end < n:
        #If we found negative then add it to neg num list (Calculations)
        if arr[end] < 0:
            neg_nums.append(arr[end])
        
        #increase end pointer till we did not reach window size    
        if((end - start + 1) < k):
            end += 1
            
        #if window size is hit
        elif ((end - start + 1) == k):
            
            #check that neg num list is not empty
            if len(neg_nums) > 0:
                result.append(neg_nums[0])
                
                #to remove all calc check first element with start pointer
                if arr[start] == neg_nums[0]:
                    neg_nums.pop(0)
            
            #no neg ele present in window    
            else:
                result.append(0)
            
            #move both pointer in forward dir to maintain window    
            start += 1
            end += 1
            
    return result
    
arr = [12, -1, -7, 8, -15, 30, 18, 28]
n = len(arr)
k = 3
ans = firstNegativeNumber(arr, n, k)
print(ans)

3) Count occurrence of Anagram

Problem statement - Given a string and a pattern string. your task is to find all the occurrence of anagram (Pattern) in a string. The anagram must be in continuous characters in string (no other character in between is allowed otherwise the size of both will differ)

👉 Now we all know to implement brute force approach over sliding window so from now we will not discuss brute force approach because we hope that you can easily implement.

Example

First input contains a string and send line of input contains second string which is a anagram (pattern) whose anagram you need to count in first string.


Identification of problem that belongs to sliding window technique

Identify the problem is of sliding window is very important so we know the problem is of array or substring and we are asked to check a substring in a string. Now we are not given window size in question. But if you think the anagram must present in a continuous order in an string It means that the anagram length and given pattern length in string will be same and we need to check that many character with given pattern hence the pattern length is only the window size so the problem is of sliding window.

💡Approach to find count of Anagram in string

The sorted order of given pattern and substring in given string will be same of length k (anagram length). Now The problem is automatically solved after this statement.

  • Initialize two pointers to maintain window and initially points at 0 index.
  • Start iterating in string using end pointer and add the current character in current substring till we did not hit the size of window.
  • As window size is hit, check that the sorted order of both current substring and given pattern is equal then increase the count and move in forward direction. The step can also be done like you can also use map to store count of each character of substring and pattern and compare them using one loop.

💻 Code - Now let us code the algorithm. Try to implement on your own without taking reference of below snippet.

def CountAnagram(strng, pattern, n):
    k = len(pattern) #window size
    start = 0
    end = 0
    ans = 0
    
    while end < n:
        if((end - start + 1) < k):
            end += 1
            
        elif ((end-start + 1) == k):
            curr_anagram = strng[start:end+1]
            if(sorted(curr_anagram) == sorted(pattern)):
                ans += 1
                
            start += 1
            end += 1
            
    return ans
    
s = "forxxorfxdofr" #  "aabaabaa"
pattern = "for" # "aaba"
n = len(s)
print(CountAnagram(s, pattern, n))

4) Maximum of all subarray of size k

Problem statement - Given an array of N integers and an integer K (window size). Your task is to find the maximum element of each subarray of size K in an array.

Example

  • First line denotes the length of array.
  • second line contains array elements
  • third line contains an integer K denoting size of window.


💡Approach

After solving top 3 problems in fixed size sliding window this question you can implement easily. Take the reference of  first negative integer problem and attain it. So by now you must identify it is a sliding window problem. We will require one resultant list to store the elements.

  • First we have two pointers initially pointing at first position. start iterating using end pointer till size of array.
  • We will also define one temporary supportive list that will hold current maximum elements that we found white iterating. So check that if temporary list is empty or the current element is greater then temporary last element. If it happens then remove all elements from temporary because we found new maximum element and add it to list.
  • Till we did not reach window size the step second and third continues.
  • As we hit window size add temporary first element to resultant array. After that remove the previous calculations using start pointer and slide the window.

💻 Code - Let us implement the code of the problem.

def FindMaximumOfSubarray(arr, n, k):
    if k > n:
        return [max(arr)]
        
    ans = []
    temp = []
    start = 0
    end = 0
    
    while end < n:
        if len(temp) == 0:
            temp.append(arr[end])
        
        else:
            while len(temp) != 0 and temp[-1] < arr[end]:
                temp.pop()
                
            temp.append(arr[end])
            
        if ((end - start + 1) < k):
            end += 1
            
        elif ((end - start + 1) == k):
            ans.append(temp[0])
            if arr[start] == temp[0]:
                temp.pop(0)
                
            start += 1
            end += 1
            
    return ans

👊 These are the top coding problems in fixed size sliding window and now if any problem encounters in similar category that you can identify and implement the approach and code. Now we will move forward with the article and take some examples of variable size sliding window technique and understand it in more depth and how both techniques differ. In variable size sliding window the size of window will not be given in question and can be of any length.✊

5) Find Largest subarray of sum k 

Problem Statement ~ Given an array of N integers and an integer K. your task is to find the length of longest subarray the sums equal to K.

🎯This is completely different problem statement then first one because there you have a fixed size subarray and there you are asked to find maximum sum but here sum is fixed and you have to find the length of subarray that can be of any length.

Example


💡Approach to find longest subarray sums equal to K

First let us understand the difference between fixed size problems and variable size problems in detail to identify the problems in future which type of algorithm to use. So here we are given a sum but in previous problem we have to find the sum. And In previous problem we know window size but here we need to find the window size. and its name only suggest that the window size will be variable.

🎯 The approach of implementation is almost similar that we have to iterate using two pointer and we have to keep continue iterating till we did not hit the required sum. And when we hit the required sum the size of window is denoted by (end - start + 1) through which we will find the length of subarray and update maximum length. While iterating if we reach sum greater then required sum than we will remove the element using start pointer (a little bit same iteration what we did in previous article on two pointer technique sum problems)

  1. First you have two pointer initially pointing at first position.
  2. Iterate using end pointer till size of array.
  3. calculation is to add the element at current position and check for three condition.
  4. If sum is less then require sum then keep iterating (increase end pointer)
  5. If we hit the require sum then update the window size and slide the window.
  6. if the sum is greater then required sum then remove calculation of first element using start pointer.

💻 Code - Implementing the approach now is very easy. If you did not understand the approach or difference between both the technique then I will request to solve the sample input with algorithm on paper and everything will be clear.

def MaximumSizeSubarrayOfSumK(arr, n, k):
    start = 0
    end = 0
    max_len_subarray = 0 #to store subarray length
    curr_sum = 0 #temp calculations
    
    while end < n:
        #calculations
        curr_sum = curr_sum + arr[end]
        
        #check if curr_sum is less then K then continue sliding
        if curr_sum < k:
            end += 1
            
        #If we hit the required sum update max window size
        elif curr_sum == k:
            max_len_subarray = max(max_len_subarray, (end - start + 1))
            
            #slide the window
            end += 1
            
        #if curr_sum greater then k then remove prev calculations
        elif curr_sum > k:
            curr_sum = curr_sum - arr[start]
            start += 1
            end += 1
            
    return max_len_subarray
    
arr = [4, 1, 1, 1, 2, 3, 5]
n = len(arr)
k = 5
print(MaximumSizeSubarrayOfSumK(arr, n, k))

Difference between Fixed size sliding window and Variable size sliding window

  1. Window size is fixed in fixed size sliding window while window size is variable and keeps on changing.
  2. Solving fixed size questions are easy because after hitting window size first time you can maintain the size and continuously you get the candidates (subarray) to check for answer. But in variable size you will not get candidate continuously and you need to check for multiple condition and window size will keep on changing.
  3. This is reason why fixed size sliding window is easy to solve in one go and variable size sliding window seems a little bit hard to approach.

6) Longest Substring without repeating Characters

This is one interesting problem statement and now we will increase out level and solve different interesting problems in variable size sliding window.

Problem statement - Given a string of N characters. your task is to find the longest substring with no repeating characters. In simple words find a substring where each character occur exactly one time because this only means non-repeating which means all unique characters.

👉 The problem statement is very similar to one that we have solved in coding problems on string and problem named is longest substring with K unique characters. If you have not gone through that problem then you can find it here and do read it. The difference between both the problem is there we have to find longest substring with K unique character and the character can repeat any number of time but here we want longest substring of all unique characters.

Example


💡Approach to find longest substring with all unique characters

👉 I hope that you have read the approach of K unique character problem because the approach and implementation is same. In previous problem we have string and we are checking that the size of map should be less than or equal to K and we find the maximum window size. So here we are comparing window size again K that means k unique characters. 

👉 But here we want all unique characters which means the size of map must be equal to window size because all the character should appear only once in substring and this will happen when map will contain character with single count the length of substring (window) will also same hence we can use this condition to find longest substring with all unique characters and the condition is true update the maximum length.

👉 One more condition to change is in previous problem we are checking that if the map size is greater then K in sense if we got any new character then we remove the previous calculations and make it equal to K. But here we want all unique so If we can encounter new character but if any repeated character is encountered then the size of map will be less then window size and this is condition which we need to check and remove previous calculations and make window size equal.

💻 Code ~  You should implement the code of this because only one condition difference is there else everything is same. And you can also use set instead of map but using map is more convenient.

def longestSubstrWithoutRepeating(strng, n):
    start = 0
    end = 0
    max_substr_len = 0 #store maximum length
    hashmap = dict()   #store count of characters
    
    while end < n:
        curr_ch = strng[end]
        if curr_ch in hashmap:
            hashmap[curr_ch] += 1
            
        else:
            hashmap[curr_ch] = 1
            
        
        #If map length equal to window size
        #so we get the substr with all unique characters
        if len(hashmap) == (end - start + 1):
            max_substr_len = max(max_substr_len, (end - start + 1))
            
        #if map length less then window size
        #so we encounder duplicates and remove them
        if len(hashmap) < (end - start + 1):
            while len(hashmap) < (end - start + 1):
                ch_front = strng[start]
                hashmap[ch_front] -= 1
                
                if hashmap[ch_front] == 0:
                    del hashmap[ch_front]
                    
                start += 1
                
        #update end pointer
        end += 1
        
    return max_substr_len
    
s = "pwwkew"
n = len(s)
print(longestSubstrWithoutRepeating(s, n))

7) Minimum window substring

This is very much interesting problem statement and lies under hard category problems. If you are able to understand and implement this problem then almost all the questions of sliding window you can easily build.

Problem statement - Given two strings as S and T. your task is to find the minimum substring length in which all the character of T occur in at least same quantity. More number of character can be there.

Example

  • First line contains first string.
  • Second line contains second string.
  • You have to return the length of minimum substring or sometime you have to also return the substring so we will see both the things in code.

💡Sliding window Approach to find Minimum window length substring

We need to keep track of how many characters of substring we have gone through so the best data structure to maintain the count is map. The basic approach is we need minimum substring that has all characters of T string in same or more quantity so we will store the count map of T string and iterate through given string S and if we found character that is in T string then we will decrease the count of character in map. The same we need to do repetitively till all the character count become zero in map. To check that character count becomes 0 most of will use one more loop but we need to optimize here so we will use one count variable that keep track of map size and as it becomes 0 we will update the answer.

  • First we will make the count map of T string.
  • Use two pointer using end pointer we will iterate till string size.
  • Check that if current character is present in map pr not. If present then decrease the count in map by 1. If any character count in map become 0 then we will decrease the map size by 1. If any character count become 0 and some character are still remaining to find in substring and if we encounter the character that has already become 0 then also decrease it by 1.
  • When we have obtained all character of T means map size becomes 0 then using start pointer we will optimize the length so we will find is there any extra character present in window that we can remove. To remove check element at start pointer present in map. If present then increase the count.

💻 Code - Let us code the algorithm

def minimumSubstringWindow(strng, t):
    count_map = dict()
    n = len(strng)
    
    for ch in t:
        if ch in count_map:
            count_map[ch] += 1
            
        else:
            count_map[ch] = 1
            
    
    start = 0
    end = 0
    map_size = len(count_map)
    min_window_len = 1000000007
    maxStart = 0
    maxend = 0
    
    while end < n:
        if strng[end] in count_map:
            count_map[strng[end]] -= 1
            
            if count_map[strng[end]] == 0:
                map_size -= 1
                
        while map_size == 0:
            min_window_len = min(min_window_len, (end - start + 1))
            maxStart = start #substring start index
            maxend = end+1  #substring end index
            
            ch_start = strng[start]
            if ch_start in count_map:
                count_map[ch_start] += 1
                if count_map[ch_start] > 0:
                    map_size += 1
                    
            start += 1
            
        end += 1
        
    print("substring start index {} and end index {}".format(maxStart, maxend))
    return min_window_len
    
s = "TOTMTAPTAT"
t = "TTA"
print("Min window len: ", minimumSubstringWindow(s, t))

END NOTES

Congratulations! to you if you have followed the article till end and tried to solve each question. Now I am assure that you can deal with any sliding window problem and implement the approach. So let us quickly conclude the important points we learned throughout the series.

  • We have studied about fixed size sliding window and variable size sliding window and identification of sliding window problems.
  • You have to use fixed-size sliding window when window size is given and use variable size sliding window window size is asked in question.
  • When you encounter such questions in interview then always first tell brute-force to interviewer and then show how you can optimize it using sliding window.

Hope you enjoyed the tutorial on sliding window. If you have any doubt or query feel free to post it in comment section below. And you can also send your query, suggestions, or the topic on which you want more articles through this contact form.

Thank you for your time! 😊

Tags:

Post a Comment

If you have any doubt or suggestions then, please let me know.

Previous Post Next Post