Do you think IIT Guwahati certified course can help you in your career?
Introduction
The Sliding window technique is used to find subarrays in an array that satisfy specific criteria. It is a subset of dynamic programmingand forms a basis for many vital questions frequently asked in programming interviews.
The technique can be applied to a problem where we have to find the maximum or minimum value for a function that calculates the answer repeatedly for a set of values from the array.
Why Use the Sliding Window Technique?
The significant advantage of this technique is that it reduces the time required to complete a task(related to a fixed subarray). Problems that would usually take O(N3) or O(N2) timeto solve with brute forcecan be solved in O(N) time using this approach because it avoids repetitive calculations, resulting in improved runtime efficiency.
Let us take an example to be more precise.
Problem Statement
Consider an array ‘ARR’ of size ‘N.’ Your task is to calculate the maximum sum of ‘K’ consecutive elements in the array.
Example-
ARR[5] = {4, -1, 0, 3, -4}
K = 2
Maximum sum = 3 (Obtained by adding values on index 0 and 1).
2. ARR[7] = { 0, 23, -12, 10, 24, -17, 9 }
K = 3
Maximum sum = 22 (Obtained by adding values on indexes 2,3 and 4).
Let us first analyze the problem with the brute force approach, and then we will discuss the Sliding Window Technique so that we can easily understand the advantage of this approach.
Brute Force Approach
In this approach, we can find the sum of all subarrays of length ‘K’ and return the maximum sum among all the calculated sums.
Starting with the first index, we calculate the sum till the Kth element and do this for all possible consecutive blocks consisting of K elements using a nested loop.
The outer loop starts with the first index, while the inner loop is used, to sum up till the Kth element.
Implementation
Program
// C++ program to implement Brute force technique.
#include <bits/stdc++.h>
using namespace std;
// Function to return the maximum sum in a subarray of size 'k'.
int maximumSum(vector<int> &arr, int n, int k)
{
// If the total number of elements is less than 'k,’ it is invalid.
if (n < k)
{
cout << "Invalid values entered.";
return -1;
}
// Initializing the variables.
int maxSum = INT_MIN;
int curSum;
// Calculating the sum of first 'k' elements in the array using a nested for loop.
for (int i = 0; i <= n - k; i++)
{
curSum = 0;
for (int j = i; j < i + k; j++)
{
curSum += arr[j];
}
maxSum = max(maxSum, curSum);
}
return maxSum;
}
int main()
{
vector<int> arr;
int n, i, a, k;
// Taking user input.
cout << "Enter the number of elements:\n";
cin >> n;
cout << "Enter the value of k\n";
cin >> k;
cout << "Enter the elements\n";
for (i = 0; i < n; i++)
{
cin >> a;
arr.push_back(a);
}
// Calling the function.
cout << "The maximum sum of a subarray of size " << k << " is " << maximumSum(arr, n, k);
return 0;
}
You can also try this code with Online C++ Compiler
The Sliding Window Technique is an optimization method used to reduce time complexity in problems involving subarrays or substrings. It works by maintaining a window of size K that moves across an array, updating results efficiently.
Compute the sum of the first K elements and store it in curSum.
Set maxSum equal to curSum initially.
Slide the window one step to the right by removing the first element and adding the next.
Update maxSum if curSum is greater.
Repeat until the window reaches the end of the array.
To understand this concept, we assume the array to be a window of length N and a block of the array as the windowpane of a fixed length K.
The pane slides over the window, performing operations on the sub-arrays and subsequently storing the required result in a variable.
The technique provides an optimal solution, and here are the steps that need to be followed:
The first K elements are added, and their sum is stored in the variablecurSum,which denotes the sum of the current elements in the block. This is the first sum and is considered to be maximum initially. So, it is stored in the variable maxSum.
Since the size of the windowpane is K, it slides one place to the right, and the curSum is updated, removing the first element of the previous block and including the last element of the current block.
If the current sum is larger than the maximum, the maxSum is updated, and the above step is repeated till it reaches the last block of the array.
The above-given steps will become more apparent with the help of an example.
Example:
Let us consider an array, ARR, with N = 7, and K = 3. We have to find the maximum sum of a subarray of length K in the array.
ARR[7] = {0, 23, -12, 10, 24, -17, 9}
K = 3
1)
curSum= ARR[0] + ARR[1] + ARR[2]
= 0 + 23 + (-12)
= 11
maxSum = 11
2)
curSum = curSum - ARR[0] +ARR[3]
= ARR[1] + ARR[2] + ARR[3]
= 23 + (-12) + 10
= 21
maxSum = max(21,11) = 21
3)
curSum = curSum - ARR[1] +ARR[4]
= ARR[2] + ARR[3] + ARR[4]
= (-12) + 10 + 24
= 22
maxSum = max(22,21) = 22
4)
curSum = curSum - ARR[2] +ARR[5]
= ARR[3] + ARR[4] + ARR[5]
= 10 + 24 + (-17)
= 17
maxSum = max(22,17) = 22
5)
curSum = curSum - ARR[3] +ARR[6]
= ARR[4] + ARR[5] + ARR[6]
= 24 + (-17) + 9
= 16
maxSum = max(22,16) = 22
Thus, the maximum sum of a subarray of length 3 is equal to 22.
Implementation
Program
// C++ program to implement Sliding Window Technique.
#include <bits/stdc++.h>
using namespace std;
// Function to return the maximum sum in a subarray of size 'k'.
int slidingWindow(vector<int> &arr, int n, int k)
{
// If the total number of elements is less than 'k', it is invalid.
if (n < k)
{
cout << "Invalid values entered.";
return -1;
}
// Initializing the variables as 0.
int maxSum = 0;
int curSum = 0;
// Calculating the sum of first 'k' elements in the array.
for (int i = 0; i < k; i++)
{
curSum += arr[i];
}
// Initially, the maximum sum is equal to the curSum.
maxSum = curSum;
/*Computing the sum of remaining windows by
adding the last element of the current window
and removing the first element of the previous window.*/
for (int i = k; i < n; i++)
{
curSum += arr[i] - arr[i - k];
maxSum = max(maxSum, curSum);
}
return maxSum;
}
int main()
{
vector<int> arr;
int n, i, k, a;
// Taking user input.
cout << "Enter the number of elements:\n";
cin >> n;
cout << "Enter the value of k:\n";
cin >> k;
cout << "Enter the elements:\n";
for (i = 0; i < n; i++)
{
cin >> a;
arr.push_back(a);
}
// Calling the function.
cout << "The maximum sum of a subarray of size " << k << " is " << slidingWindow(arr, n, k);
return 0;
}
You can also try this code with Online C++ Compiler
Enter the number of elements:
7
Enter the value of k:
3
Enter the elements:
0
23
-12
10
24
-17
9
Output:
The maximum sum of the subarray of size 3 is 22.
Time Complexity
Since this approach uses a single for loop, which iterates over the array from 1 to N, the time complexity is given by O(N).
Space Complexity
It uses constant space to solve the problem. Thus the space complexity is given by O(1).
Types of Sliding Window
The Sliding Window Technique is categorized into two main types based on the window size:
1. Fixed Size Sliding Window
In this approach, the window size K remains constant throughout the traversal. It is commonly used in problems where we need to process subarrays or substrings of a fixed length.
How it Works:
Compute the sum (or required value) for the first K elements.
Slide the window one step at a time by removing the first element and adding the next.
Update the result as needed and continue until the end of the array.
Use Case Example:
Finding the maximum sum of K consecutive elements in an array.
2. Variable Size Sliding Window
In this approach, the window size varies dynamically based on problem constraints. It is useful for problems where we need to find subarrays or substrings that satisfy a given condition.
How it Works:
Expand the window by adding elements until the condition is met.
If the condition is violated, shrink the window by removing elements from the left.
Continue adjusting the window while keeping track of the required result.
Use Case Example:
Finding the smallest subarray with a sum ≥ S.
Both approaches optimize performance by reducing redundant computations, making them highly efficient for solving array and string problems.
Basic Steps to Solve Sliding Window Problems
The Sliding Window technique is a common approach used to optimize problems related to arrays or strings by creating a window that slides over the data. It helps to reduce the time complexity by avoiding redundant computations.
1. Understand the Problem Statement Clearly
Identify what the problem requires, such as finding the maximum sum of subarrays, the length of a substring, or meeting a specific condition.
Determine if the window size is fixed (e.g., "size k") or variable (depends on conditions like sum or unique elements).
2. Initialize the Window Parameters
Set up variables to hold initial results (e.g., sum, maxSum, or count).
Initialize pointers like start and end for dynamic sliding windows or iterate through indices for fixed ones.
3. Expand the Window
For variable windows, increase the window size by moving the end pointer forward. Add the current element to the window’s calculation.
4. Shrink the Window When Needed
Adjust the start pointer when the window condition is violated (e.g., window size exceeds k, or sum becomes too large).
Subtract the element at the start from the window's calculation and then increment start.
5. Update the Result
Check if the current window meets the condition, and update the result (like maximum sum or longest length) accordingly.
Continue sliding until the end of the array is reached.
6. Return the Final Result
After completing the sliding process, return the result stored during each iteration.
Example Code for Fixed Window Size
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int maxSumSubarray(vector<int>& arr, int k) {
int sum = 0, maxSum = 0;
// Calculate the sum of the first window
for (int i = 0; i < k; i++) {
sum += arr[i];
}
maxSum = sum;
// Slide the window through the array
for (int i = k; i < arr.size(); i++) {
sum += arr[i] - arr[i - k]; // Add the next element and remove the first element of the current window
maxSum = max(maxSum, sum); // Update the maximum sum if the current window's sum is greater
}
return maxSum;
}
int main() {
vector<int> arr = {1, 3, 5, 2, 8, 9, 3};
int k = 3;
cout << "Maximum sum of subarray with size " << k << ": " << maxSumSubarray(arr, k) << endl;
return 0;
}
You can also try this code with Online C++ Compiler
The sliding window algorithm is a technique used to solve problems involving arrays or lists, by examining a subset of elements in a sliding window.
What is the sliding window technique formula?
The sliding window formula involves maintaining a window of fixed size, adjusting it by adding new elements and removing old elements as it slides.
What is sliding window protocol with example?
The sliding window protocol is used in networking to manage data transmission. For example, sending packets while keeping track of unacknowledged packets in a buffer.
Conclusion
In this article, we discussed the Sliding Window technique, a powerful approach used to optimize problems involving arrays and strings. By maintaining a dynamic window, this technique reduces time complexity and improves efficiency in solving problems like maximum subarray sum, longest substring, and more. Understanding and applying the Sliding Window approach can significantly enhance problem-solving skills in competitive programming and real-world applications.
34+ registered 
