The Sliding Window Technique is an algorithmic approach designed to substitute nested loops with a solitary loop, thereby decreasing the time complexity.
Sliding Window Technique
Let's employ a comparison to aid in understanding this approach. Imagine a panel securely positioned within a window that has a width of n and a height of k.
Combine the array arr with n elements within the window, along with the current sum of k elements in the pane, positioned at the starting point which is 0 units to the left. As the window is pushed, it will move one unit distance at a time, covering the subsequent k elements in the pane.
Examples of how to apply the sliding window technique
Example:
To achieve our objective, we aim to obtain the maximum sum of the initial "k" elements within an integer array of size "n".
Input :arr[] = {100, 200, 300, 400}, k = 2
Output : 700
Input :arr[] = {1, 4, 2, 10, 23, 3, 1, 0, 20}, k = 4
Output : 39
We achieve the highest total by including the subarray {4, 2, 10, 23} with a length of 4.
Input :arr[] = {2, 3}, k = 3
Output : Invalid
There are no subarrays of size 3 available since the total array size is 2.
Naive Approach:
Let's proceed with examining the issue by employing the Brute Force Strategy. We iterate through the elements incrementally up to the kth element commencing from the initial index. Each consecutive group of k items or blocks that can be contiguous is processed in this manner. The inner loop within the nested for loops of this approach will iterate up to the k-th element. The commencement of the outer for loop occurs at the first element within the block of k items.
Think about the following application:
#include <bits/stdc++.h>
using namespace std;
int maxSum(int arr[], int n, int k)
{
int maximum_sum = INT_MIN;
for (int i = 0; i < n - k + 1; i++) {
int curr_sum = 0;
for (int j = 0; j < k; j++)
curr_sum = curr_sum + arr[i + j];
maximum_sum = max(curr_sum, maximum_sum);
}
return maximum_sum;
}
int main()
{
int arr[] = { 11, 6, 7, 10, 6, 3,11, 0, 20 };
int k = 4;
int n = sizeof(arr) / sizeof(arr[0]);
cout<<maxSum(arr, n, k);
return 0;
}
Output
As demonstrated in the code snippet above, containing a pair of nested loops, the time complexity is O(k*n).
Consider a window of size n containing a fixed pane of size k to grasp the concept of the sliding window method. Note that initially, the pane is positioned at the far left, precisely 0 units from the left edge. Now, establish a correlation between the window and an array arr with n elements, and the pane representing the current sum of k elements. When we shift the window, it advances by one unit. Consequently, the subsequent k elements will be encompassed by the pane.
Using the sliding window method
We employ a linear iteration to compute the total of the initial k terms from n, saving the outcome in the variable window sum. Subsequently, as we monitor the maximum sum, we iteratively traverse through the array until reaching its conclusion.
Add the final item from the present block to the initial item of the previous block in order to determine the total sum of the current set comprising k elements.
The window shifts across the array as demonstrated in the following example.
#include <iostream>
using namespace std;
int maxSum(int arr[], int n, int k)
{
if (n < k) {
cout<< "not valid";
return -1;
}
int maximum_sum = 0;
for (int i = 0; i < k; i++)
maximum_sum += arr[i];
int window_sum = maximum_sum;
for (int i = k; i < n; i++) {
window_sum += arr[i] - arr[i - k];
maximum_sum = max(maximum_sum, window_sum);
}
return maximum_sum;
}
int main()
{
int arr[] = { 11, 6, 7, 10, 6, 3,11, 0, 20 };
int k = 4;
int n = sizeof(arr) / sizeof(arr[0]);
cout<<maxSum(arr, n, k);
return 0;
}
Output
Now that we have identified that our code contains a single loop, it is evident that the Time Complexity is linear. As a result, the Time Complexity is represented as O(n).
