Open-Source Internship opportunity by OpenGenus for programmers. Apply now.
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
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.
