Simple and Best Explanation on Sliding Window Algorithm with Diagram

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 sub-array or sub-string 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 problem-solving technique that is generally applied to given an array list or string. Here word window is generally referred to the size of the sub-array or sub-string you need to find, and sliding simply means looping through the entire array or string to find that suitable window size.

Note – A sub-array or sub-string 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 set-size 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, 

Fixed-size window

In fixed-size 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 variable-size 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 variable-size windows that you can use to identify and decide your approach,

Also read, Introduction to Recursion – Learn In The Best Way with JavaScript | Part 1

How to approach a Fixed-size and Variable size Window

Fixed-size Window Solving Framework

• At first, we will initialize the end and start 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 the start variable index gets out of scope with respect to window size.
  • Now we increase the start and end variables to slide forward the window.
• 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++ 
  }
  
}

Variable-size Window Solving Framework

• At first, we will initialize the end and start 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.
• 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 and start to track window size, minOperation variable to store a final number of operations and count 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 the count value by 1.
• The second condition checks, if we have reached the given window size K or not, if yes! then we store the current count value to the final number of operations minOperation
  • 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.
• 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 and start to track window size, list to store negatives number at the current window and res 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 end-start + 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.
• 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 and start 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 and start to track window size, queue data structure to store the maximum number at the current window and res 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 increase end by 1.
• If we reach the given window size K, then we will simply push the first element of the queue inside our res 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 and start to track window size, sum to track the current subarray sum, and max 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 than k, which is desired sum, we have to remove the elements from starting position to bring down the sum either equal to k or lesser than k.
• If the current sum gets equal to k, we will check and store the current subarray size, end-start+1 to the max variable.
• But if neither condition is satisfied which means currently our sum is less than k, then will simply increase the end variable to add more elements to the sum.
• Finally, returns the max variable which is holding the largest subarray sum of size k.

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 and start to track window size, map data-structure to track the number of unique characters, and longest 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 than k,(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 to k, we will check and store the current subarray size, end-start+1 to the longest variable.
• But if neither condition is satisfied which means currently our map size is less than k, then will simply increase the end variable to add more elements to the map.
• 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

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.

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 and start to track window size, set data structure to track the number of unique characters, and longest 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 the set.
  • Now we will store the current length of the set, to longest variable.
  • and move forward the window size by increasing end by 1.
• If the element already present in the set,
  • then we would simply remove the element at start index.
  • and move forward start by 1.
• 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.