Welcome to another blog of the series “Understanding Data Structure and Algorithms with JavaScript 🚀”. The sliding window algorithm is one of the most popular techniques in order to find the suitable subarray or substring for a given problem. It helps reduce the use of nested loops into a single loop, thus decreasing the time complexity of your program.
In this article, we will learn, the origin, identify if the problem can be solved using sliding windows or not, and different types of sliding windows with examples.
Why Sliding Window Algorithm is Important
Sliding Window Algorithms is basically a problemsolving technique that is generally applied to given an array list or string. Here word window is generally referred to the size of the subarray or substring you need to find, and sliding simply means looping through the entire array or string to find that suitable window size.
Note – A subarray or substring is a continuous part of an array or string.
In order to understand the importance and efficiency of the algorithms let us understand it through an example,
Maximum Sum of a given subarray of size k
We have to find the maximum sum value of the given subarray size of k,
Example: Input: nums = [9, 2, 2, 5, 3, 8, 1, 4, 7], k = 3 Output: 10
Explanation: Maximum sum is (5  3  8) = 10
Brute Force Approach
function sumSub(nums,k){ let sum = 0 let max = 0 for(let i = 0; i < nums.length  k; i++){ for(let j = i; j < k+i; j++){ sum+=nums[j] } max = Math.max(max, sum) sum = 0 } return max } let res = sumSub([9, 2, 2, 5, 3, 8, 1, 4, 7], 3) console.log(res) // 10
In the brute force approach, we use a nested for loop where the outer loop iterate from starting index 0
till nums.length  k
, and in the inner loop iterate with a window size of k, thus the time complexity of the above program is O(n * k).
Also read, A comparison of Supabase, Hasura and Aista
Sliding Window Approach
function sumSub(nums,k){ let sum = 0 for(let i = 0; i < k; i++){ sum+=nums[i] } let max = sum for(let j = k; j < nums.length; j++){ sum = sum + nums[j]  nums[j  k] max = Math.max(max, sum) } return max } let res = sumSub([9, 2, 2, 5, 3, 8, 1, 4, 7], 3) console.log(res) // 10
In the Sliding window approach, instead of maintaining nested loops, we use two loops, in which first we simply calculate the sum of the first subarray/window, and then in the second loop we just iterate from k
index to nums.length
, add the current element, and remove the previous element.
As we use two single loops instead of nested, the time complexity of the above program is O(n).
Also read, Simple Explanation of Sorting Algorithms with JavaScript  Part 2
How to Identify a Sliding Window Problem
Now the critical question rises! “How do you Identify a problem that can be solved using Sliding Window Method?“, Here are a few points you can use to identify if the given question can be solved using Sliding Window Algorithm:
 The first thing you have to look at is if you are given an array or string
 Then there should be something related to finding a subarray or substring because the sliding window algorithm can be applied only on some continuous setsize of array or string.
 It may also ask for the largest/maximum or minimum size
 It may also have k (window size) or sometimes they might ask you to find the window size! like,
 Find the largest window or smallest window with some condition
 Example – find the largest subarray/window size which equals the sum 5.
In the end, it all depends on experience, the more questions you solve, the better your instincts get in finding if the given question can be solved using Sliding window or not!
Also read, Basic operations in Graph Data structure
Types of Sliding Window Problems
Basically, Siding Window Problems have two types,
Fixedsize window
In fixedsize window problems, generally, we are already provided with a subarray or substring size and we have to find the maximum sum/product or minimum sum/product. These types of problems are more common and easier to solve than other ones.
Variable size window
In variablesize window problems, you are provided with the targeted sum, product, maximum vowels, or some condition in which you have to return the maximum or minimum window size. These types of problems are less common and a little tough to solve than other ones as you might need to use different algorithms or data structures to solve them.
Also read, Simple Explanation of Tree traversal Operations with JavaScript
Difference between Fixed and Variable Sliding Window
There are a few notable differences between fixed and variablesize windows that you can use to identify and decide your approach,
Fixedsize window  Variable size window 



Also read, Introduction to Recursion – Learn In The Best Way with JavaScript  Part 1
How to approach a Fixedsize and Variable size Window
Fixedsize Window Solving Framework
 At first, we will initialize the
end
andstart
variables with the first index of the given array/string, these two variables will be used to track down the window size.  In the loop condition, we will run the
end
variable to the end of the given array/string.  We would keep on increasing the value of the
end
till we don’t acquire the given array/string/window size.  Once we hit the window size, we will calculate our answer.
 Now we have to slide the window size, in order to do that, we have to remove the element present at the
start
variable index. As we have to slide forward, the element at thestart
variable index gets out of scope with respect to window size.  Now we increase the
start
andend
variables to slide forward the window.
 Now we have to slide the window size, in order to do that, we have to remove the element present at the
 Finally, we return our answer.
// intialize our window variables let start = 0 let end = 0 /* run the loop till our end variable doesnt touches size of given array */ while(end < size){ // we do the given calcultions calculations /* we will increase end variable till our window size (end  start + 1) is lesser than given desired size. */ if(windowSize < k){ end++ }else if(windowSize < k){ /* Once we reach the desired window size we will calculate our answer, remove the elment present out of the socpe and move forward our sliding window */ ans > calculations if(check if elemt is out of scope){ remove the elment } //move forward our window size start++ end++ } }
Variablesize Window Solving Framework
 At first, we will initialize the
end
andstart
variables with the first index of the given array/string, these two variables will be used to track down the window size.  In the loop condition, we will run the
end
variable to the end of the given array/string.  We would keep on increasing the value of the
end
till we don’t acquire the given condition.  Once we met our condition, we would calculate and return our result and move forward with window size.
 But, if our calculation becomes greater than the given condition,
 Then we will use a while loop to remove the elements present at the
start
variable index to minimize or equal to a given condition.  move forward with window size.
 Then we will use a while loop to remove the elements present at the
 Finally, we return our answer.
// intialize our window variables let start = 0 let end = 0 /* run the loop till our end variable doesnt touches size of given array */ while(end < size){ // we do the given calcultions calculations /* till our condition is not met we will keep on increasing the window size */ if(contd < k){ end++ /* once our conditon is met, we will calculate our answer and move forward with our window size */ }else if(contd == k){ ans > calculations end++ /* But if our condition become greater than k, then we have to remove unnesscarry elements and move forward with our window size*/ }else if(contd > k){ while(contd > k){ remove the elements which are of scope start++ } end++ } }
Also read, Basic operations in Graph Data structure
Few Examples of Sliding Window Problems with Solutions
Minimum Recolors to Get K Consecutive Black Blocks
Type: Fixed Window Size
Question
You are given a string blocks
, where blocks[i]
is either 'W'
or 'B'
, representing the color of the i
^{th} block.
You are also given an integer k
, which is desired number of window sizes in which all the letters are 'B'
.
Return the minimum number of operations to convert 'W'
to 'B'
in K window size subarray.
Link: Leetcode link
Examples
Input: blocks = "WBBWWBBWBW", k = 7 Output: 3
Explanation:
One way to achieve 7 consecutive black blocks is to recolor the 0th, 3rd, and 4th blocks so that blocks = "BBBBBBBWBW". It can be shown that there is no way to achieve 7 consecutive black blocks in less than 3 operations. Therefore, we return 3.
Explanation
 First, we initialize a few variables, like
end
andstart
to track window size,minOperation
variable to store a final number of operations andcount
to store the current number of operations.  At the start of the loop, we will check if the current element is
'W'
, if yes we will increase thecount
value by 1.  The second condition checks, if we have reached the given window size
K
or not, if yes! then we store the currentcount
value to the final number of operationsminOperation
 Then we check if we have
'W'
at our starting/left side of our window size, as now we will be forwarding our window slide and we don’t want extra'W'
,  If yes! then decrease the current count,
 Move forward to the left position by 1.
 Then we check if we have
 Finally, after the end of the loop, returns the final number of operations
minOperation
.
Code
var minimumRecolors = function(blocks, k) { let minOperation = Infinity let count = 0 let start = 0 let end = 0 while(end < blocks.length){ if(blocks[end] == 'W'){ count++ } if(end  start + 1 == k){ minOperation = Math.min(minOperation, count) if(blocks[start] == 'W'){ count } start++ } end++ } return minOperation };
Also read, Simple Explanation of Tree traversal Operations with JavaScript
First Negative Number in every Window of Size K
Type: Fixed Window Size
Question
You are given an array of size n with a set window size of K, you have to return all the first negative numbers for each window Size.
Examples
Input: nums = [1,3,1,3,5,3,6,7], k = 3 Output: [1,1,1,3,0,0] Explanation:
Window position Max   [1 3 1] 3 5 3 6 7 1 1 [3 1 3] 5 3 6 7 1 1 3 [1 3 5] 3 6 7 1 1 3 1 [3 5 3] 6 7 3 1 3 1 3 [5 3 6] 7 0 1 3 1 3 5 [3 6 7] 0
Explanation
 First, we initialize a few variables, like
end
andstart
to track window size,list
to store negatives number at the current window andres
to return the final result.  Then we add a negative number to the list. At a particular point in time, the list holds negative numbers which are there in the current running window and not all the negative elements in the array. So, that we can retrieve the first negative number from the current window.
 If endstart + 1 is smaller than k, we keep increasing the end.
 When we reached the window size, we need to perform two operations:
 We’re checking if the list is empty or not. If it is empty, then there is no negative number in the current window. In that case, we’ll push 0 in the
res
array.  If it’s not empty, then the first element in the list is the first negative number of the current window., pushing that into the
res
array.
 We’re checking if the list is empty or not. If it is empty, then there is no negative number in the current window. In that case, we’ll push 0 in the
 Second, we need to slide the window. For that, we need to remove the first element of the current window and add the next element from the array to the window. But before removing the first element, we need to check whether it belongs to the list or not. If it belongs to the list, we need to remove it from the list, as it will not be a part of our next window.
 So, if the first element is found to be a negative number, then we have to remove it from the list, and this number is happened to be the front element of the list.
 Then, increment the values of
end
andstart
to slide the window.
Code
var firstNegative = function(nums, k) { let start = 0 let end = 0 let res = [] let list = [] while(end < nums.length){ if(nums[end] < 0){ list.push(nums[end]) } if(end  start + 1 < k){ end++ }else if(end  start + 1 == k){ if(list.length == 0){ res.push(0) }else{ res.push(list[0]) if(nums[start] == list[0]){ list.shift() } } start++ end++ } } return res }; let arr = [1,3,1,3,5,3,6,7] let windowSize = 3 let result = firstNegative(arr, windowSize) console.log(result) //[1, 1, 1, 3, 0, 0]
Also read, Understanding Binary Search Trees with Js
Maximum of all subarrays of size k
Type: Fixed Window Size
Question
You are given an array, there is a sliding window of size k
which is moving from the very left of the array to the very right. You have to return the maximum number in each particular subarray when the window shifts from left to right.
Link: Leetcode link
Examples
Input: nums = [1,3,1,3,5,3,6,7], k = 3 Output: [3,3,5,5,6,7] Explanation: Window position Max   [1 3 1] 3 5 3 6 7 3 1 [3 1 3] 5 3 6 7 3 1 3 [1 3 5] 3 6 7 5 1 3 1 [3 5 3] 6 7 5 1 3 1 3 [5 3 6] 7 6 1 3 1 3 5 [3 6 7] 7
Explanation
 First, we initialize a few variables, like
end
andstart
to track window size,queue
data structure to store the maximum number at the current window andres
to return the final result.  At the start of the loop, we will run a while loop to find the maximum number at the current window.
 If we have an element present in the queue and the current element is greater than the elements present inside the queue then we will remove the element.
 Now, just push the element inside the
queue
.  Unless
end
variable reaches the given window size, we will simply going to increaseend
by 1.  If we reach the given window size K, then we will simply push the first element of the
queue
inside ourres
array.  Then before shifting our window size, we will check if the first element of the
queue
is equal to the element we will be leaving then we will simply remove that element from the queue and then shift the window size by 1 position.  Finally, return your
res
array.
Code
var maxSlidingWindow = function(nums, k) { let start = 0 let end = 0 let queue = [] let res = [] while(end < nums.length){ while (queue.length  1 >= 0 && nums[end] > queue[queue.length  1]){ queue.pop(); } queue.push(nums[end]); if(end  start + 1 < k){ end++ }else if(end  start + 1 == k){ res.push(queue[0]) if(nums[start] == queue[0]){ queue.shift() } start++ end++ } } return res };
Also read, Introduction to Tree Data Structure
Largest Subarray of sum K
Type: Variable Window Size
Question
Given an array and a sum k, we need to print the length of the longest subarray that sums to k.
Examples
Input: arr = {7,1,6,0}, k = 7 Output: Length of the longest subarray with sum K is 3 Explanation: 1 + 6 + 0 = 7, it is the longest subarray with sum 7 and length 3.
Explanation
 First, we initialize a few variables, like
end
andstart
to track window size,sum
to track the current subarray sum, andmax
to store the maximum subarray size.  At the start of the loop, we would first try to calculate the current sum.
 If the current
sum
is greater thank
, which is desired sum, we have to remove the elements from starting position to bring down thesum
either equal tok
or lesser thank
.  If the current
sum
gets equal tok
, we will check and store the current subarray size,endstart+1
to themax
variable.  But if neither condition is satisfied which means currently our
sum
is less thank
, then will simply increase the end variable to add more elements to the sum.  Finally, returns the
max
variable which is holding the largest subarraysum
of sizek
.
Code
function largetSubarray(nums, k){ let start = 0 let end = 0 let sum = 0 let max = 0 while(end < nums.length){ sum+=nums[end] if(sum > k){ while(sum > k){ sum=nums[start] start++ } end++ }else if(sum == k){ max = Math.max(max, end  start + 1) end++ }else{ end++ } } return max } let arr = [2,3,8,1,9] let res = largetSubarray(arr, 12) console.log(res) // 3
Also read, Simple Explanation of Stack and Queue with JavaScript
Longest Substring With K Unique Characters
Type: Variable Window Size
Question
Given a string you need to return the longest possible substring that has exactly K unique characters. If there is more than one substring of the longest possible size, then return any one of them.
Link: Leetcode
Examples
Input: Str = “aabbcc”, k = 1 Output: 2 Explanation: Max substring can be any one from {“aa” , “bb” , “cc”}.
Explanation
 First, we initialize a few variables, like
end
andstart
to track window size,map
datastructure to track the number of unique characters, andlongest
to store the longest subarray size.  At the start of the loop, we would first try to record the current element frequency by strong it into
map
.  If the current
map
size is greater thank
,(means we have more than k unique characters), then we have to remove the elements from starting position to bring down the map size to either equal or lesser than k.  If the current
map
size gets equal tok
, we will check and store the current subarray size,endstart+1
to thelongest
variable.  But if neither condition is satisfied which means currently our
map
size is less thank
, then will simply increase the end variable to add more elements to themap
.  Finally, returns the
longest
variable which is holding the longest substring with K unique characters.
Code
function kUniqueChar(s, k) { let start = 0; let end = 0; let longest = 0; let map = new Map(); while (end < s.length) { if (!map.has(s[end])) { map.set(s[end], 1); } else { map.set(s[end], map.get(s[end]) + 1); } if (map.size > k) { while (map.size > k) { if (map.get(s[start]) > 1) { map.set(s[start], map.get(s[start])  1); } else { map.delete(s[start]); } start++; } end++; } else if (map.size == k) { longest = Math.max(longest, end  start + 1); end++; } else { end++; } } return longest; } let str = "ababcbcca"; let res = kUniqueChar(str, 2); console.log("final answer >", res); // 2
Also read, Easy Explanation of Linked list Data Structure in JavaScript
Max Consecutive Ones III
Type: Variable Window Size
Question
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.Examples
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.
Explanation
 If you read the question, we have been given constraints that we can only flip maximum k 0’s, which means we can only flip either less or equal to k 0’s digits.
 First, we will initialize two variables
end
andstart
to track down the variable window size.  In our loop, at first, we will check if the current element
nums[end]
, is equal to 0 or not! and If yes, then we decrease the value of K.  And in our second if condition we will check that if our window size has more than K 0, then we will shift by one position from the left edge using the
start
variable. Through this process, we try to remove any extra number of 0 greater than k.  Then move the end to the next position regardless of whether we had a 1 or a 0.
 Finally returns the window size.
Code
var longestOnes = function(nums, k) { let end = 0 let start = 0 while(end < nums.length){ if(nums[end] == 0){ k } if(k < 0){ if(nums[start] == 0){ k++ } start++ } end++ } return end  start };
Also read, Simple Explanation on Sorting Algorithms with JavaScript  Part 1
Longest Substring With Without Repeating Characters
Type: Variable Window Size
Question
Given a string s
, return the length of the longest substring without repeating characters.
Link: Leetcode
Examples
Input: s = "abcabcbb" Output: 3 Explanation: The answer is "abc", with the length of 3.
Explanation
 First, we initialize a few variables, like
end
andstart
to track window size,set
data structure to track the number of unique characters, andlongest
to store the longest subarray size.  At the start of the loop, we would first try to record the current element frequency by strong it into
set
, If the
set
doesn’t consist of that element we would add it to theset
.  Now we will store the current length of the
set
, tolongest
variable.  and move forward the window size by increasing
end
by 1.
 If the
 If the element already present in the
set
, then we would simply remove the element at
start
index.  and move forward
start
by 1.
 then we would simply remove the element at
 Finally, returns the
longest
variable which is holding the longest substring with no repeating characters.
Code
var lengthOfLongestSubstring = function(s) { let start = 0 let end = 0 let longest = 0 let mySet = new Set(); while(end < s.length){ if(!mySet.has(s[end])){ mySet.add(s[end]) longest = Math.max(mySet.size, longest)
end++ }else{ mySet.delete(s[start]) start++ } } return longest }; let str = "ababcbcca" let res = lengthOfLongestSubstring(str) console.log(res) // 3
Also read, Introduction to Recursion – Learn In The Best Way with JavaScript  Part 1
Final Words
Sliding Window Algorithms may come as a little fancy but believe me it is beneficial in optimizing your solution. If you like my article, share it with your friends and colleagues and check out more articles of the series “Understanding Data Structure and Algorithms with JavaScript 🚀” and articles on various topics like Javascript, React, and Java.
Leave a Reply