Sliding Window problems involve moving a fixed or variable-size window through a data structure, typically an array or string. This technique is used to efficiently solve problems based on continuous subsets of elements. It's particularly useful when we need to find subarrays or substrings that meet specific conditions.

#1 What is Sliding Window Pattern?

The Sliding Window Technique is a method used to efficiently solve problems involving sub-arrays or sub-strings. It involves defining a window or range in the input data and then moving that window across the data to perform some operation within the window.

Subarrays = A subarray of an array is a contiguous segment of the array. It means that it consists of a contiguous block of elements from the original array. For example, if you have an array [1, 2, 3, 4], then [1, 2], [2, 3, 4], and [3, 4] are all examples of subarrays.

Substrings = A substring of a string is a contiguous sequence of characters within that string. Unlike subarrays, substrings are taken from strings. For example, if you have a string "hello", then "he", "ell", and "lo" are all examples of substrings.

• Subarrays are related to arrays, while substrings related to strings.

Let's take an example to understand this properly. Suppose we have an array of size N and an integer K. Our task is to calculate the maximum sum of a subarray with exactly K elements.

One way to solve this problem is by taking each subarray of size K from the array and finding out the maximum sum of these subarrays. However, this approach would result in nested loops, leading to a time complexity of O(N^2).

Here's how you can implement this approach using nested loops in C++:

#include <iostream>
#include <vector>

using namespace std;

int maxSubarraySum(vector<int>& arr, int k) {
    int maxSum = INT_MIN;
    int n = arr.size();

    for (int i = 0; i <= n - k; i++) {
        int windowSum = 0;
        for (int j = i; j < i + k; j++) {
            windowSum += arr[j];
        }
        maxSum = max(maxSum, windowSum);
    }

    return maxSum;
}

int main() {
    vector<int> arr = {4, 2, 1, 7, 8, 1, 2, 8, 1, 0};
    int k = 3;
    cout << "Maximum sum of a subarray of size " << k << ": " << maxSubarraySum(arr, k) << endl;
    return 0;
}

Although this approach works, it has a time complexity of O(N^2), which is not efficient for large arrays.

But this is not the optimized approach?

Instead of taking each K sized subarray and calculating its sum, we can just take one K size subarray from 0 to K-1 index and calculate its sum now shift our range one by one along with the iterations and update the result, like in next iteration increase the left and right pointer and update the previous sum.

It significantly reduces the time complexity to O(N), making the solution much more efficient.

Here's how you can implement the more efficient way using sliding window technique in C++:

The sliding window pattern can be implemented using loops, either for or while.

#include <iostream>
#include <vector>

using namespace std;

int maxSubarraySum(vector<int>& arr, int k) {
    int maxSum = INT_MIN; // Initialize maxSum to the smallest possible integer value
    int windowSum = 0;    // Initialize the sum of the current window to 0
    int left = 0;         

    // Loop through the array from left to right
    for (int right = 0; right < arr.size(); right++) {
        windowSum += arr[right]; // Add the current element to the window sum

        // If the window size is equal to k
        if (right >= k - 1) {
            maxSum = max(maxSum, windowSum); // Update maxSum with the maximum of maxSum and windowSum
            windowSum -= arr[left];          // Subtract the leftmost element of the window from windowSum
            left++;                          // Slide the window to the right by incrementing left
        }
    }

    return maxSum; // Return the maximum sum
}

int main() {
    vector<int> arr = {4, 2, 1, 7, 8, 1, 2, 8, 1, 0};
    int k = 3;
    cout << "Maximum sum of a subarray of size " << k << ": " << maxSubarraySum(arr, k) << endl;
    return 0;
}

OR

#include <iostream>
#include <vector>

using namespace std;

int maxSubarraySum(vector<int>& arr, int k) {
    int maxSum = INT_MIN; // Initialize maxSum to the smallest possible integer value
    int windowSum = 0;    // Initialize the sum of the current window to 0
    int left = 0;
    int right = 0;         

    // Loop through the array from left to right
    while (right < arr.size()) {
        windowSum += arr[right]; // Add the current element to the window sum
        right++;                 // Expand the window to the right

        // If the window size is equal to k
        if (right - left == k) {
            maxSum = max(maxSum, windowSum); // Update maxSum with the maximum of maxSum and windowSum
            windowSum -= arr[left];          // Subtract the leftmost element of the window from windowSum
            left++;                          // Slide the window to the right by incrementing left
        }
    }

    return maxSum; // Return the maximum sum
}

int main() {
    vector<int> arr = {4, 2, 1, 7, 8, 1, 2, 8, 1, 0};
    int k = 3;
    cout << "Maximum sum of a subarray of size " << k << ": " << maxSubarraySum(arr, k) << endl;
    return 0;
}

This implementation has a time complexity of O(N), which is much more efficient compared to the nested loop approach.

Visualization:

Array: [4, 2, 1, 7, 8, 1, 2, 8, 1, 0]
         ^  ^  ^
         |__|__|
          maxSum = 7

         [4, 2, 1]  -->  maxSum = 7
         [2, 1, 7]  -->  maxSum = 10
         [1, 7, 8]  -->  maxSum = 16
         [7, 8, 1]  -->  maxSum = 16
         [8, 1, 2]  -->  maxSum = 16
         [1, 2, 8]  -->  maxSum = 18
         [2, 8, 1]  -->  maxSum = 18
         [8, 1, 0]  -->  maxSum = 18

Maximum sum of a subarray of size 3 = 18

#2 Real World Example

Imagine you have a big, yummy sandwich, but you can only take small bites at a time. So, to enjoy the whole sandwich, you take one bite, then slide your mouth a bit to take another bite, and keep doing that until you finish the whole sandwich.

That's exactly how the sliding window pattern works in programming!

Here's how it works:

1. Imagine you have an array or a string: Think of it like your big sandwich. It's something you want to take "bites" out of.
2. Define the window size: Decide how big each "bite" will be.
3. Start taking "bites": Begin from the start of your array or string and take your first "bite".
4. Slide your window: Move your starting point to the next position and take another "bite", then another, until you reach the end.
5. Do something with each "bite": You can do different things with each "bite" you take. Maybe you want to find the maximum or minimum of each "window", or maybe you want to find a specific pattern.

Let's try an example:

Say we have an array [1, 3, -1, -3, 5, 3, 6, 7] and we want to find the maximum sum of 3 consecutive elements.

We start with the first 3 elements: [1, 3, -1], and find their sum, which is 3. That's our first "bite".

Then we slide our window one step to the right: [3, -1, -3], and find the sum again, which is -1. That's our second "bite".

We keep doing this until we've taken all the "bites".

#3 Type of Sliding Window

The Sliding Window technique can be further categorized into different types based on the specific problem we are solving and how the window moves through the array or string. Here are the common types of sliding window techniques:

1 Fixed Size Window:

In this type, the size of the window remains constant throughout the process. We move the window by one element at a time and perform operations within the fixed-size window.

The general steps to solve these questions by following below steps:

• Find the size of the window required, say K.
• Compute the result for 1st window, i.e. include the first K elements of the data structure.
• Then use a loop to slide the window by 1 and keep computing the result window by window.

Example Problem: Finding the maximum sum of a subarray of size K.

2 Variable Size Window:

In this type, the size of the window can vary based on certain conditions. We adjust the size of the window dynamically according to the problem requirements.

The general steps to solve these questions by following below steps:

• In this type of sliding window problem, we increase our right pointer one by one till our condition is true.
• At any step if our condition does not match, we shrink the size of our window by increasing left pointer.
• Again, when our condition satisfies, we start increasing the right pointer and follow step 1.
• We follow these steps until we reach to the end of the array.

Example Problem: Finding the smallest subarray with a sum greater than or equal to a given value.

#3 How to Identify Sliding Window Problems?

Sliding window problems typically involve finding maximum or minimum subarrays or substrings that satisfy specific conditions. The size of the subarray or substring, represented by 'K', is often given in the problem statement.

While these problems can be solved using nested loops with a time complexity of O(N^2), employing the sliding window technique allows us to solve them more efficiently with a time complexity of O(N).

• Problem Type: Finding Maximum/Minimum Subarray or Substrings with specific conditions.
• Given: Size of subarray or substring 'K'.
• Time Complexity: O(N) or O(Nlog(N)).
• Constraints: N <= 10^6 (where N is the size of the array or string).