Sliding Window Problem – C++ Implementation

Board Infinity -

Introduction

The sliding window is a highly innovative method for resolving certain challenging issues using an array or string. It is frequently used to change the problem's O (n2) time complexity to O (n).

Maintaining a window that complies with the problem limitations is the core principle. Two pointers, such as left and right, that point to a certain index in an array or a specific character in the case of a string can be used to represent a window. If the window violates any of the problematic characteristics, it is said to be "unstable."

The window then makes an attempt to regain stability by contracting (decreasing the left pointer) or extending (incrementing the right pointer). Until the issue is resolved, the procedure is continued.

Ways to Use the Sliding Window Technique to Solve Problems

The following examples show how sliding window technique is generally used:

  1. Determine the necessary window size.
  2. Create the first window's result, starting from the data structure's beginning.
  3. Next, slide the window by 1 using a loop, and keep calculating the outcome window by window.

Example: Our goal is to determine the largest sum of the first 'k' consecutive integers in an array of size 'n' integers.

Input  : arr[] = {100, 200, 300, 400}, k = 2

Output : 700

Input  : arr[] = {2, 3}, k = 3

Output : Invalid

As the size of the whole array is 2, there isn't a subarray of size 3.

Situation Analysis

Consider a window with a length of n and the pane that is fixed in it with a length of k to best understand the approach. Take into account that the pane is originally at the very left, or 0 units from the left. Now, tie the window to the n-element array arr[] and the pane to the k-element current sum. If we now exert force on the window, it will move a unit of distance forward.

Applying Sliding Window technique

We use a linear loop to calculate the sum of the first k terms out of n, and we store the result in the variable window sum.

  1. Then, while concurrently keeping track of the largest sum, we shall linearly graze across the array until it reaches its end.
  2. Simply add the final element of the current block to the first element of the preceding block to obtain the current total of the block of k items.

Code

#include <iostream>
using namespace std;

int maxSum(int arr[], int n, int k)
{
    // n must be greater
    if (n < k) {
        cout << "Invalid";
        return -1;
    }
 
    // Compute sum of first window of size k
    int max_sum = 0;
    for (int i = 0; i < k; i++)
        max_sum += arr[i];
 
    int window_sum = max_sum;
    for (int i = k; i < n; i++) {
        window_sum += arr[i] - arr[i - k];
        max_sum = max(max_sum, window_sum);
    }
 
    return max_sum;
}
 
int main()
{
    int arr[] = { 1, 4, 2, 10, 2, 3, 1, 0, 20 };
    int k = 4;
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << maxSum(arr, n, k);
    return 0;
}

Output: 24

Below are some of the top interview questions that take advantage of the sliding window technique.

  1. Determine the longest substring of a string with k distinct characters that is given.
  2. Discover every substring of a string that is its permutation.
  3. Find the longest substring of the input string that contains unique characters.
  4. Determine the longest continuous one sequence possible
  5. Find the smallest sum subarray of the given size, k.

This concludes the article about the Sliding window technique. Hopefully, after understanding it with ample examples in our article you can put it to good use to solve challenging DSA problems!

write your code here: Coding Playground