What is the sliding window algorithm?

The sliding window algorithm is a technique used to solve problems that involve arrays/lists. It is a very efficient technique that can be used to solve problems in linear time complexity.

The sliding window algorithm is very efficient because it only iterates through the array/list once. This means that the time complexity of the algorithm is linear, O(n).

When to use the sliding window algorithm?

The sliding window algorithm is used to solve problems that involve finding the longest/shortest substring, subarray, or a desired value in an array/list. The problems that can be solved using the sliding window algorithm are usually problems that involve a linear data structure such as an array or a linked list.

How to implement the sliding window algorithm?

The sliding window algorithm can be implemented in many different ways. The most common way is to use two pointers, one at the beginning of the window and one at the end of the window. The window is defined by these two pointers. The window can either increase or decrease its size depending on the problem. We can also use multiple windows in some cases.

Let's understand using examples...

Question: Find the sum of all subarrays of size K of a given array.

The first approach is to use a nested for loop to iterate through all the subarrays of size k and find their sum. This approach has a time complexity of O(n*k) and a space complexity of O(1).

int sumOfSubarrays(int arr[], int n, int k) {
    int sum = 0;
    for (int i = 0; i <= n - k; i++) {
        int currentSum = 0;
        for (int j = i; j < i + k; j++) {
            currentSum += arr[j];
        }
        sum += currentSum;
    }
    return sum;
}

The disadvantage of this approach is that it is not very efficient because it has a time complexity of O(n*k). This means that it will take a lot of time to find the sum of all subarrays of size k in an array of size n.

The second approach is to use a sliding window to find the sum of all subarrays of size k. This approach has a time complexity of O(n) and a space complexity of O(1).

int sumOfSubarrays(int arr[], int n, int k) {
    int sum = 0;
    for (int i = 0; i < k; i++) {
        sum += arr[i];
    }
    int currentSum = sum;
    for (int i = k; i < n; i++) {
        currentSum += arr[i] - arr[i - k];
        sum += currentSum;
    }
    return sum;
}

Steps :

• The first step is to find the sum of the first k elements of the array.

• This can be done by using a for loop to iterate through the first k elements of the array and adding them to a variable called sum.

• The second step is to use a sliding window to find the sum of all subarrays of size k.

• This can be done by using a for loop to iterate through the array and adding the current element to the current sum and subtracting the element that is k elements before the current element from the current sum.

• The third step is to return the sum of all subarrays of size k.

Template For Sliding Window

// using for loop

public int slidingWindow(int[] nums){
    int left = 0;
    int right = 0;

    for( ; right < nums.length; right++){
        // grow window
        ...

        // shrink window
        for( ; left <= right && isWindowInvalid() ; left++){
            // update window
        }
    }
}

// using while loop

public int slidingWindow(int[] nums){
    int left = 0;
    int right = 0;

    while(right < nums.length){
        // update window
        ...

        // shrink window
        while(left <= right && isWindowInvalid() ){
            // update window
            ...
        }

        right++;
    }
}

This template is very useful for solving problems. We can solve many of the sliding window problems using this template.

Let's rewrite the solution for our above Question: Find the sum of all subarrays of size K of a given array.

// using for loop

public int sumOfSubarrays(int arr[], int n, int k){
    int left = 0;
    int right = 0;
    int ans = 0;

    for( ; right < nums.length; right++){
        // grow window
        ans += arr[right];

        // shrink window
        for( ; r - l + 1 > k ; left++){
            // update window
            ans -= arr[left];
        }
    }
    return ans;
}

We haven't used left <= right condition in the inner loop because we know that left <= right is always true. but we can also use it.

Our isWindowInvalid() function is replaced by this r - l + 1 > k condition. This condition is true when the window size is greater than k.

When the window size is greater than k, we need to shrink the window. So, we are shrinking the window until the window size is less than or equal to k.

This is the sliding window algorithm template. We can solve many of the sliding window problems using this template.

Some Leetcode Problems Related To Sliding Window

1. 713. Subarray Product Less Than K

2. 3. Longest Substring Without Repeating Characters

3. 1493. Longest Subarray of 1's After Deleting One Element

4. 1838. Frequency of the Most Frequent Element

5. 2379. Minimum Recolors to Get K Consecutive Black Blocks

If you want any kind of help with the above questions then you can use my GitHub Repo.

These are some of the problems, there are many more on Leetcode.

Conclusion

In this article, we have solved the problem: Find the sum of all subarrays of size K of a given array using the sliding window algorithm. We have also learned the sliding window algorithm template. We can solve many of the sliding window problems using this template. I hope you have enjoyed this article. If you have any doubts or suggestions then please comment below.

LinkedIn : https://www.linkedin.com/in/kenil-kanani-5ab300219/

Twitter: https://twitter.com/kenil_kanani_16