Do not miss this exclusive book on Binary Tree Problems. Get it now for free.

In this article, we will discuss about the sliding window technique and how it is useful while solving problems.

Table of Contents:

Introduction to Sliding Window
Idea of sliding window
Examples of sliding window
How to identify sliding Window Questions
Questions set for sliding window pattern

Introduction to Sliding Window

The sliding window pattern is a common technique used to solve problems involving arrays or strings.As its name suggest, it takes subset of data from given arrays or strings,shrinking and expanding that data based on question demand which gives sliding effect.

Idea of sliding window

We take two pointer start and end,and we keep incrementing the end pointer
If the end pointer make our window invalid then we keep incrementing left pointer which will shrink our window till the window once again become valid.
then we will update the result the by our valid window

for(end = 0; end < n; end++):
    update window with element at end pointer
    while (condition not valid):
        remove element at start pointer from window, move start pointer to the right
    update result

Examples of Sliding Window

Example 1.You are given an integer array.You have to find sum of every subarray of size K.

Input: arr = [1,3,7,-6,5,6],k=3
Output: [11,4,6,5]

Approach
1.This is a sliding window question where we have to find sum of every element in window of size k.
2.So, first we start adding element till we add k element and store result.
3.Then, we subtract the leftmost element and add the upcoming right element while traversing the array and store result in array.
4.We repeat step 3 till we calculate sum of every subarray of size k.

Solution :-

#include <bits/stdc++.h>

using namespace std;

void subarraySum(vector<int>&arr , vector<int>&res, int k){
    int windowStart = 0;
    int currentWindowSum = 0;
    

    for (int windowEnd = 0; windowEnd < arr.size(); windowEnd++) {
        currentWindowSum += arr[windowEnd]; // adding element to our window 
        while (windowEnd - windowStart ==  k-1) {
            //when we get sum of k element we add sum to our answer vector
            res.push_back(currentWindowSum);
            currentWindowSum -= arr[windowStart]; //we subtract leftmost element from the window
            windowStart++;//increment the windowstart 
        }
    }
}

int main() {
   int n;//size of vector
   int k;
   cin>>n>>k;
   vector<int> arr(n);
   //taking input in vector
   for(int i=0;i<n;i++){
       cin>>arr[i];
   }
   vector<int>res;//for storing result of every subarray
   subarraySum(arr,res,k);//calling function to calculate subarray sum
   //PRINTING OUTPUT
   for(int i=0;i<res.size();i++){
       cout<<res[i]<<' ';
   }
   
}

Output :-

11 4 6 5

Time Complexity - O(n-k) ~ O(n) we loop over array n-k times
Space Complexity -O(n-k) for our result array

Lets take a look at another example

Example 2.You are given an integer array nums consisting of n elements, and an integer k.Find a contiguous subarray whose length is equal to k that has the maximum average value and return this value

Input: nums = [1,12,-5,-6,50,3], k = 4
Output: 12.75000
Explanation: Maximum average is (12 - 5 - 6 + 50) / 4 = 51 / 4 = 12.75

Approach:-
1.If you observe closely this is sliding window question where we have to find average of every window of size k.
2.So, first we create window of size k and calculate the sum of first window and store avg of this window.
3.Now,we have to increment and shrink the window so we will add new element from right side to the window and subtract leftmost element from the window.
4.Now, we repeat Step 3 for full array traversal and keep updating our maximum average of window size k.

Solution:-

#include <bits/stdc++.h>

using namespace std;

double findMaxAverage(vector<int>& nums, int k) 
    {
        
        double maxAverage = INT_MIN;//minimum value in int range
       
        double curTotal = 0.0;
        for (int i = 0; i < k; i++) {
            curTotal += nums[i];//first window sum
        }
        maxAverage = max(maxAverage, curTotal / k);
        // Travel the sliding window
        for (int i = k; i < nums.size(); i++) {
            curTotal -= nums[i - k]; // subtracting leftmost element of window
            curTotal += nums[i];//adding new element to window
            maxAverage = max(maxAverage, curTotal / k);//finding avg of every window
        }
    
        return maxAverage;
    }

int main() {
    int n;//size of vector nums
    int k;
    cin>>n>>k;
   vector<int> nums(n);
   for(int i=0;i<n;i++){
       cin>>nums[i];
   }
   double average = findMaxAverage(nums,k);//calling function for finding  max  average
   cout<<"maximum average of subarray of size k is : " <<average;
   
}

Output:

maximum average of subarray of size k is : 12.75

Time Complexity - O(n) where n is the size of array
Space Complexity -O(1)

Lets take a look at another question of sliding window,this can be little tricky.

Example 3 - Given a string s, find the length of the longest substring without repeating characters.

Input: s = "abcabcbb"
Output: 3
Explanation: The answer is "abc", with the length of 3

Approach:-
1.If you observe carefully you find that this is a sliding window question where we have to keep increasing our window till we don't have any duplicate letter in our window and if we get duplicate letter in our window then we start shrinking the window.
2.First we will create an Unordered_map for storing frequency of every letter.
Note: For unordered_map reference visit Unordered_map
3.We traverse the string and insert every character of string in map and keep increasing our window.
4. If we encounter character which is already present in the map then we start decreasing the window by removing left index element.
5. By repeating Step 3 and 4 and updating our answer we will get the final answer.

Solution:-

#include <bits/stdc++.h>

using namespace std;

int lengthOfLongestSubstring(string s)
        {
            if (s.size() < 2) return s.size();//if size is 1 we return size
            int left = 0;
            
            int maxlen = 0;//final answer variable
            //using map for storing frquency of characters
            unordered_map<char, int> map; 
            for (int right = 0; right < s.size(); right++)
            {
                map[s[right]]++; // increasing count of every character
                while (map[s[right]] > 1)
                {
                //if we get charcter whose count is greater than 1
                //we start  shrinking the window
                    map[s[left]]--;
                    left++;
                }
                //finding maximum length of substring while window is valid
                maxlen = max(maxlen, right - left + 1);
            }
            return maxlen;
        }

int main() {
   string s;
   cin>>s;
   
   int maxlength = lengthOfLongestSubstring(s);//calling function for finding longest substring with distinct letters
   
   cout<<"maximum length of substring with distinct letter is : " <<maxlength;
   
}

Output :-

maximum length of substring with distinct letter is : 3

Time Complexity -O(n) where n is the size of string
Space Complexity -O(min(n,m)) where n is the size of string and m is the maximum element present in map

How to identify Sliding Window Question

So we will be to generally identify the sliding window pattern if we observe carefully

The problem involves a data structure that is ordered and iterable like arrays, strings, etc.
The problem is asking to find a subrange in an array/strings,continuous smallest,largest,average or target value.
There is naive or brute force approach which will run in O(n^2),O(n^3)or somewhat larger time complexity.

Sliding Window Questions Set

Max Consecutive Ones
Problem discription : 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 0's.
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
Count Number of Nice Subarrays
Problem discription :Given an array of integers nums and an integer k. A continuous subarray is called nice if there are k odd numbers on it
Input: nums = [1,1,2,1,1], k = 3
Output: 2
Explanation: The only sub-arrays with 3 odd numbers are [1,1,2,1] and [1,2,1,1]
Print all subarrays of an array having distinct elements
Problem discription :Given an integer array, print all maximum size subarrays having all distinct elements in them
Input: A[] = { 5, 2, 3, 5, 4, 3 }
Output: The largest subarrays with all distinct elements are:
{ 5, 2, 3 }
{ 2, 3, 5, 4 }
{ 5, 4, 3 }
Find the count of distinct elements in every subarray of size k
Problem discription :Given an array and an integer k, find the count of distinct elements in every subarray of size k.
Input: arr[] = { 2, 1, 2, 3, 2, 1, 4, 5 }, k = 5;
Output:
The count of distinct elements in subarray { 2, 1, 2, 3, 2 } is 3
The count of distinct elements in subarray { 1, 2, 3, 2, 1 } is 3
The count of distinct elements in subarray { 2, 3, 2, 1, 4 } is 4
The count of distinct elements in subarray { 3, 2, 1, 4, 5 } is 5
Minimum Size Subarray Sum
Problem discription :Given an array of positive integers nums and a positive integer target, return the minimal length of a subarray whose sum is greater than or equal to target. If there is no such subarray, return 0 instead.
Input: target = 7, nums = [2,3,1,2,4,3]
Output: 2
Explanation: The subarray [4,3] has the minimal length under the problem constraint
Permutation in String
Problem discription :Given two strings s1 and s2, return true if s2 contains a permutation of s1, or false otherwise.
In other words, return true if one of s1's permutations is the substring of s2
Input: s1 = "ab", s2 = "eidbaooo"
Output: true
Explanation: s2 contains one permutation of s1 ("ba")
Find All Anagrams in a String
Problem discription :Given two strings s and p, return an array of all the start indices of p's anagrams in s. You may return the answer in any order.
Input: s = "cbaebabacd", p = "abc"
Output: [0,6]
Explanation:
The substring with start index = 0 is "cba", which is an anagram of "abc".
The substring with start index = 6 is "bac", which is an anagram of "abc"

This are some practice problems on sliding window given them try.

With this article at OpenGenus, you must have the idea about how to approach Sliding Window Technique Questions.