Thursday, September 21, 2023
HomeData Structures and AlgorithmSimple and Best Explanation on Sliding Window Algorithm with Diagram

# 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).

#### 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).

## 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.

## 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,

Fixed-size window Variable size window
• In the given problem, We will always be provided with window sizes like a subarray size.
• For example, We have to find the maximum sum value of the given subarray size of k.
• The focus is more on the window size.
• Easy than the variable-size windows, as maintaining window size is simple.
• In the given problem, instead of window size, we will be provided with some conditions like maximum sum or minimum sum.
• For example, We have to find the maximum sum value of the given subarray size of k.
• The focus is more on the element present inside the window size.
• Little hard than the fixed-size windows, as maintaining window size is complex.

## 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
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.

#### 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
};```

### 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)
if(nums[start] == list){
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]```

### 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.

#### 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)
if(nums[start] == queue){
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```

### 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.

#### 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```

### Max Consecutive Ones III

Type:- Variable Window Size

#### Question

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.

#### 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` and `start` 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
};```

### 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.

#### 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])){
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```

## 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. Aaquib Ahmedhttps://aaquib.netlify.app
Hi, I'm Aaquib Ahmed, a passionate self-taught frontEnd web developer based in Bangalore, India. I tend to make use of modern web technologies to build websites that look great, feels fantastic, and functions correctly. I am especially focusing on Reactjs.
RELATED ARTICLES