Sliding Window Technique

7 min readFeb 15, 2022

When one hears of a Sliding Window, the first thing that comes to mind is a sliding window like the one on the above image and if that is what is in mind , then you are on the right track.

The sliding window technique solves some dynamic programming questions whose knowledge will help you find it easier to solve most questions.

So what is Sliding window technique :

I mean, if you were trying to explain this term to a kid, how would you do it?I, for one, would start by showing a kid what a window is 😁😁😁😁😁 and then proceed to demonstrate how to slide it ! basically giving everyone listening an overview of what will be going on.

The above image represents the Sliding Window technique.Just like a normal sliding window, we have to slide it to adjust it to the size we want.

HOW DO YOU USE THE SLIDING WINDOW TECHNIQUE

First and foremost , you will realize that the window only holds a sub-array. A sub-array is contiguous by definition.

Here is an example that will help you understand better:

Array : [1,2,3,5,7,9,3]

Output : [2,3,5,7] //this is a sub-array its in a sequence.
         [2,3] [9,3]// Sub-arrays that form subsets.

I hope that is understandable 😁

The technique is used to find a sub-array that satisfies the given conditions ,be it Max sum, Min sum, and so on.

RECOGNIZING THESE PROBLEMS

The problem is dealt with sequentially.
If you are trying to get max,min,longest,shortest and contained values that are in a sub array.

QUESTIONS VARIETY

Finding a subarray in a fixed length.
Finding a dynamic variant
Finding a dynamic variant with the help of an auxiliary data structure(i.e Maps, arrays and etc:)

There are many more which I will update with time.

Examples of questions:-

In tech,most things are understood better when viewed, I guess seeing really is believing!

Find a sub-arrays that adds up to a desired number.

Example input : array :[1,2,3,4,5,6,7,8,9] desired number : 9

This question is a dynamic sliding window solved question and it requires you to add lets say value of index 0 being 1 plus value of index 1 being 2 till you get to 9, but for example:

1+2+3+4= 10 // Its more than 9 so what do we do??

1+2+3+4= 10 // Its more than 9 so what do we do??// We reduce the size of the window from the left by one,confirm if it now 9 which in our case it is.1+2+3+4=10 - 1 =9

What if we reduce the left most and its still not the number given?

The answer is we will keep resizing the window till we get what we want, Store what we want and return the subsets or the number of subsets.

POLITE NOTICE : BE KEEN ON WHAT THE PROBLEM REQUIRES YOU TO DO.

THE CODE STEP BY STEP:

Disclaimer : To none-JavaScript coders I will be using JavaScript but its not as different from other languages

Define the variable that will carry the subsets when the subarray satisfy the condition.

let solution = [];

2.Define the current sum to be able to keep track of the sum at the current index.

let currentsum = 0;

3. Define the start and the end of the window. At first it will be at the same point then you start sliding it towards the right . If the current sum is less than the desired sum provided then add the next index value then increment the index of the end :-

currentsum = currentsum + value of the index :

let start = 0;     
for(let end = 0; end < arr.length;){
    if(currentsum < sum){       
       currentsum += arr[end];       
       end++;
}

4. In case the currentsum goes beyond the condition we will have to reduce the window that is by subtracting the first number that is in the window.

Example : [2,3,4,5] Desired number is 7:
end is at 2 first being index 0 .Currentsum is less than desired which is 0, So add the currentsum to the index [0] being 2 now the currentsum is 2, But its still lesser than 7 so add 3 , still less, add 4 and its 9 which is more.
So we have to reduce the window and thats by
currentsum = currentsum- arr[start]
9–arr[0]= 9–2 = 7;
Then increment start cause to reduce the size of the window.

else if (currentsum > sum){        
     currentsum -= arr[start]        
     start ++;       
}

5. Finally we get a sub-array that adds to the desired value

e.g 3+4 = 7

so we need to push the sub-array and continue iterating through the array till you get to the end with is the arr.length — 1and we stated it as a condition in the for loop end<array.length cause it needs to get to one less than the length.

else{        
     solution.push(arr.slice(start,end));        
     currentsum -= arr[start];        
     currentsum += arr[end];         
     start ++;         
     end ++;        
  }       
}

So we push the sub-array by slicing it from the array using the slice() method and then change the currentsum and change the window size to continue iterating through.

6. Return the subsets pushed in the solution array.

Full code:

var DesiredSumSubArray = function(arr,sum){
let solution = [];
let currentsum = 0;
let start = 0;     
for(let end = 0; end < arr.length;){
    if(currentsum < sum){       
       currentsum += arr[end];       
       end++;
}
else if (currentsum > sum){        
     currentsum -= arr[start]        
     start ++;       
}
else{        
     solution.push(arr.slice(start,end));        
     currentsum -= arr[start];        
     currentsum += arr[end];         
     start ++;         
     end ++;        
  }       
}
return solution;
}

Time complexity : O(n). Looping through it once

Space complexity :O(n). Cause of the empty solution array

Max sum subarray of size k.

QUESTION : Given an array of integers, find maximum sum subarray of a required size.

Example Input : array : [-1, 2, 3, 1, -3, 2] subarray size : 2

In this question same implementation of the sliding window but difference is that the window has to have only 2 elements.

Taking you through the conceptual logic of this question:

I know you can use bruteforce for this question but brute force uses time complexity of O(n) and space complexity of O(n)

If you use the sliding window technique

time complexity : O(n)

Space complexity :O(1)

Difference is brought by the optimum most solution. When we use the bruteforce we tend to iterate all possible storing the sums in a hashmap the max is obviously our result but it uses linear space but in sliding window we confirm if the cursum is greater than the max and if it is then its the max.

THE CODE STEP BY STEP:

Disclaimer : To none-JavaScript coders I will be using JavaScript but its not as different from other languages

1.Defining the current sum as cursum, Initializing it with 0.

let cursum = 0;

2.Define the max sum to keep track of the maximum sum

let max = -infinity; //in case we have negative numbers.

3.Loop through the array

for(let i = 0; i<nums.length; i++){
}

4. Update the current sum example is at the start of the loop arr[0] = -1

so the cursum = cursum which is 0 + arr[0] which is -1 = -1

cursum += nums[i];

5.If the size of the window is reached we now check the maximum

if(i >= size - 1){     
  maxsum = Math.max(cursum,maxsum);     
  cursum -= nums[i - (size - 1)]; 
}

If i is greater than or equal to size — 1; why do say that;

If i gets to index 1 the size is full hence if i is 1 then we check the max so far.

maxsum = Math.max of either cursum = 1 and maxsum which is -infinity; the 1 is more hence becomes the new maxsum.

Then the cursum is reduced by deleting the first element to reduce the window and add another element.

cursum = cursum(1)-num[i(1) — (size(2)-1)]
cursum = 1 — nums[0]
cursum = 1 — -1= 0

With that the first index has being removed in the sum and loop continues till we get to the end of the array.

Then return the Max.

The full code

var Maxsubarr = function(nums,size){
let cursum = 0;
let max = -infinity; //in case we have negative numbers.
for(let i = 0; i<nums.length; i++){
   cursum += nums[i];
if(i >= size - 1){     
  maxsum = Math.max(cursum,maxsum);     
  cursum -= nums[i - (size - 1)]; 
}
}return maxsum;
};

Dynamic variant with an auxiliary data structure

Longest Substring With no more than k distinct.

By auxiliary i mean using an array,linked list or a hashmap.

This question is a leetcode question tested by giant tech companies e.g Microsoft.

Question : Given a string s and an integer k, return the length of the longest substring of s that contains at most k distinct characters.

Example Input : s = ‘eceba’ , k=2

output : 3

Explanation : The substring is “ece” with length 3.

Incase the length of the string is the same or less than the distinct number then return the length of the string.

if(k >= s.length ){         
   return s.length;     
}

2.Define an empty hash map variable.

let hmap = {}     
let max = 0;

3.Iterating through the string.

for(let right=0,left=0; right<s.length; right++){
}

4.Adding values to the hashmap while or increament its number if already present.

hmap[s[right]] = (hmap[s[right]]||0)+1;

5.Remove the left index character if the unique characters exceed the distinct values allowed.

while(Object.keys(hmap).length>k){
}

6.If the character value is 0 then delete it but if its not 0 just decrement the value by 1.

if(--hmap[s[left]] === 0){                 
    delete hmap[s[left]]             
   }             
left ++;

7.Getting the max you compare the max value and the subtraction of right e.g 6 and left e.g 4 + 1. If the subtraction is more then thats the max

max = Math.max(max,right-left+1);

Full code

var lengthOfLongestSubstringKDistinct = function(s, k) {if(k >= s.length ){         
     return s.length;     
    }
let hmap = {}     
let max = 0;
for(let right=0,left=0; right<s.length; right++){
     hmap[s[right]] = (hmap[s[right]]||0)+1;
     while(Object.keys(hmap).length>k){
if(--hmap[s[left]] === 0){                 
    delete hmap[s[left]]             
   }             
left ++;
}max = Math.max(max,right-left+1);
}
return max;}