Why was the Sliding Window Technique Developed❔
The sliding window technique was developed to efficiently solve problems involving subarrays or subsequences within arrays or strings. Many problems require analyzing continuous subsets of data, such as finding the maximum sum of a subarray or the longest substring with unique characters. However, using brute force or nested loops to explore every possible subarray can be computationally expensive, especially for large datasets.
To address these inefficiencies, the sliding window technique was introduced as a way to:
- Optimize the time complexity from O(n²) or higher (using brute force) to O(n) in many cases.
- Minimize redundant recalculations by keeping track of the current "window" of data, so we don’t need to start over with each iteration.
- Work within a single pass of the array or string, maintaining only the necessary information as the window slides across the data.
The sliding window algorithm technique is mainly used to solve subarray problems, such as finding the longest/shortest subarray that meets a specific condition.
If you use a brute-force solution, you would need to nest for loops, resulting a time complexity of O(n^2).
for (int i = 0; i < nums.size(); i++) {
for (int j = i; j < nums.size(); j++) {
// nums[i, j] is a subarray
}
}The idea behind the sliding window algorithm technique is not difficult. It involves maintaining a window that slides continuously, and then updating the answer. The general logic of this algorithm is as follows:
int left = 0, right = 0;
while (right < nums.size()) {
// expand the window
window.addLast(nums[right]);
right++;
while (window needs shrink) {
// shrink the window
window.removeFirst(nums[left]);
left++;
}
}The code written based on the sliding window algorithm framework has a time complexity of O(N), which is more efficient than the brute-force solution using nested for loops.
What Problems does Sliding Window Solve?
Sliding window is particularly effective in solving problems involving:
- Subarrays/Subsequences: Continuous parts of an array, such as finding the maximum or minimum subarray sum, or finding the smallest or largest subarray that satisfies certain conditions.
- Substrings: Continuous parts of a string, like finding the longest substring with unique characters, or determining whether a substring meets certain criteria (e.g., palindromes or containing certain characters).
- Efficiency: Sliding window optimizes problems that would otherwise require recalculating values for overlapping subarrays, reducing the time complexity to linear in most cases.
Types of Sliding Window
- Fixed-Size Sliding Window | Constant Window:
- The window size remains constant throughout the problem.
- Example: Finding the maximum sum of a subarray of size
k.
- Variable-Size Sliding Window:
- The window size can grow or shrink based on certain conditions.
- Example: Finding the smallest subarray with a sum greater than or equal to a given value.
1️⃣ Constant Window | Fixed Window Approach
The constant window approach maintains a window of a specific size and slides it across the array or string.
Concept
The goal is to calculate the sum of elements within a fixed-size window as it moves across the array. A brute-force method would involve recalculating the sum of the window each time it moves, which would lead to a time complexity of O(n * k), where n is the number of elements in the array, and k is the size of the window.
However, a more efficient approach involves updating the sum incrementally. As the window slides from left to right, the sum of the current window can be derived from the sum of the previous window by subtracting the element that is leaving the window (on the left) and adding the element that is entering the window (on the right). This reduces the time complexity to O(n).
Steps
- Initialize two pointers:
leftandright. The left pointer marks the beginning of the window, and the right pointer marks the end. - Calculate the sum of the initial window.
- Slide the window by incrementing both left and right pointers. Update the sum by subtracting the element at the left pointer and adding the element at the right pointer.
- Continue this process until the window has traversed the entire array.
Template:
fixed_window()
{
int low = 0, high = 0, windowsize = k;
while (i < sizeofarray)
{
// Step 1: Create a window that is one element smaller than the desired window size
if (high - low + 1 < windowsize)
{
// Generate the window by increasing the high index
high++;
}
// Step 2: Process the window
else
{
// Window size is now equal to the desired window size
// Step 2a: Calculate the answer based on the elements in the window
// Step 2b: Remove the oldest element (at low index) from the window for the next window
// Proceed to the next window by incrementing the low and high indices
}
}
}Dry Run:
Initialization:
maxSum = 0
windowSum = 0
k = 3 (size of window)
+-----+-----+-----+-----+-----+-----+-----+
arr = | 1 | 3 | 2 | 6 | 4 | 8 | 5 |
+-----+-----+-----+-----+-----+-----+-----+
Calculate Initial Window Sum:
Iteration 1:
maxSum = 0
windowSum = 0
k = 3
+-----+-----+-----+-----+-----+-----+-----+
arr = | 1 | 3 | 2 | 6 | 4 | 8 | 5 |
+-----+-----+-----+-----+-----+-----+-----+
0 1 2 3 4 5 6
^
|
i
i < k
0 < 3
True
windowSum = WindowSum + arr[i]
= 0 + 1
= 1
--------------------------------------------------------------
Iteration 2:
maxSum = 0
windowSum = 1
k = 3
+-----+-----+-----+-----+-----+-----+-----+
arr = | 1 | 3 | 2 | 6 | 4 | 8 | 5 |
+-----+-----+-----+-----+-----+-----+-----+
0 1 2 3 4 5 6
^
|
i
i < k
1 < 3
True
windowSum = WindowSum + arr[i]
= 1 + 3
= 4
--------------------------------------------------------------
Iteration 3:
maxSum = 0
windowSum = 4
k = 3
+-----+-----+-----+-----+-----+-----+-----+
arr = | 1 | 3 | 2 | 6 | 4 | 8 | 5 |
+-----+-----+-----+-----+-----+-----+-----+
0 1 2 3 4 5 6
^
|
i
i < k
2 < 3
True
windowSum = WindowSum + arr[i]
= 4 + 2
= 6
--------------------------------------------------------------
Iteration 4: (Loop Termination)
maxSum = 0
windowSum = 6
k = 3
+-----+-----+-----+-----+-----+-----+-----+
arr = | 1 | 3 | 2 | 6 | 4 | 8 | 5 |
+-----+-----+-----+-----+-----+-----+-----+
0 1 2 3 4 5 6
^
|
i
i < k
3 < 3
False
The loop will break.
Window Sum contains the initial window's sum.Set windowSum to MaxSum:
maxSum = windowSumSlide the Window Across the Array:
// Start from the k to upto the array's last element.
Iteration 1:
maxSum = 6
windowSum = 6
k = 3
+-----+-----+-----+-----+-----+-----+-----+
arr = | 1 | 3 | 2 | 6 | 4 | 8 | 5 |
+-----+-----+-----+-----+-----+-----+-----+
0 1 2 3 4 5 6
^
|
i
windowSum = WindowSum + arr[i] - arr[i - k]
= 6 + arr[3] - arr[0]
= 6 + 6 - 1
= 11
maxSum = max(maxSum, windowSum)
= max(6, 11)
= 11
----------------------------------------------------------
Iteration 2:
maxSum = 11
windowSum = 11
k = 3
+-----+-----+-----+-----+-----+-----+-----+
arr = | 1 | 3 | 2 | 6 | 4 | 8 | 5 |
+-----+-----+-----+-----+-----+-----+-----+
0 1 2 3 4 5 6
^
|
i
windowSum = WindowSum + arr[i] - arr[i - k]
= 11 + arr[4] - arr[1]
= 11 + 4 - 3
= 12
maxSum = max(maxSum, windowSum)
= max(11, 12)
= 12
----------------------------------------------------------
Iteration 3:
maxSum = 12
windowSum = 12
k = 3
+-----+-----+-----+-----+-----+-----+-----+
arr = | 1 | 3 | 2 | 6 | 4 | 8 | 5 |
+-----+-----+-----+-----+-----+-----+-----+
0 1 2 3 4 5 6
^
|
i
windowSum = WindowSum + arr[i] - arr[i - k]
= 12 + arr[5] - arr[2]
= 12 + 8 - 2
= 18
maxSum = max(maxSum, windowSum)
= max(12, 18)
= 18
----------------------------------------------------------
Iteration 4:
maxSum = 18
windowSum = 18
k = 3
+-----+-----+-----+-----+-----+-----+-----+
arr = | 1 | 3 | 2 | 6 | 4 | 8 | 5 |
+-----+-----+-----+-----+-----+-----+-----+
0 1 2 3 4 5 6
^
|
i
windowSum = WindowSum + arr[i] - arr[i - k]
= 18 + arr[6] - arr[3]
= 18 + 5 - 6
= 17
maxSum = max(maxSum, windowSum)
= max(18, 17)
= 18
------------------------------------------------------------
Iteration 4:
maxSum = 18
windowSum = 17
k = 3
+-----+-----+-----+-----+-----+-----+-----+
arr = | 1 | 3 | 2 | 6 | 4 | 8 | 5 |
+-----+-----+-----+-----+-----+-----+-----+
0 1 2 3 4 5 6
^
|
i
Since i has crossed the array bounds,
we done the sliding, maxSum Contains
the maximum window sum.Code:
#include <iostream>
#include <vector>
using namespace std;
int slidingWindowSum(const vector<int>& arr, int k) {
int n = arr.size();
int maxSum = 0;
int windowSum = 0;
// Calculate the sum of the initial window
for (int i = 0; i < k; ++i) {
sum += arr[i];
}
maxSum = windowSum;
// Print the sum of the first window
cout << "Sum of window 1: " << windowSum << endl;
// Slide the window across the array
for (int i = k; i < n; ++i) {
windowSum = windowSum - arr[i - k] + arr[i]; // Update the sum
cout << "Sum of window " << i - k + 2 << ": " << windowSum<< endl;
maxSum = max(maxSum, windowSum);
}
return maxSum;
}
int main() {
vector<int> arr = {1, 3, 2, 6, 4, 8, 5};
int k = 3;
int sum = slidingWindowSum(arr, k);
cout << "Max Sum Window is: " << sum;
return 0;
}
2️⃣ Variable-Size Sliding Window
🅰️ Longest subarray or substring:
The problem revolves around finding the longest subarray or substring from a given array or string, where the sum of the elements is less than or equal to a given value K. This approach is widely used in coding interviews and is based on the sliding window technique.
Initially, you might start with a brute-force approach where you generate all possible subarrays or substrings and then check each one to see if it meets the condition. However, this is inefficient and can be optimized using the sliding window technique.
The sliding window technique helps in optimizing the process by maintaining a window that expands or shrinks based on the conditions. Here's how it works:
Step-by-Step Process:
- Initialize Pointers: Start with two pointers, L (left) and R (right), both set to the beginning of the array or string. Also, initialize variables sum and maxLength to zero.
- Expand the Window: Start expanding the window by moving the R pointer. Add the element at the R pointer to sum.
- Check the Condition: If the sum is less than or equal to K, check if the current window size (R - L + 1) is the largest so far. If it is, update maxLength.
- Shrink the Window: If the sum exceeds K, start shrinking the window by moving the L pointer to the right. Subtract the element at the L pointer from sum and continue this process until the sum is less than or equal to K again.
- Continue Until the End: Repeat the above steps until the R pointer reaches the end of the array or string.
- Result: The value in maxLength at the end of the process will be the length of the longest subarray or substring that satisfies the condition.
Code:
#include<bits/stdc++.h>
using namespace std;
// Function to find the longest subarray with sum <= K
int longestSubarrayWithSum(vector<int>& arr, int K) {
int n = arr.size();
int maxLength = 0; // Initialize the maximum length to 0
int sum = 0; // Initialize the current sum to 0
int left = 0; // Left pointer for the sliding window
// Iterate over the array using the right pointer
for (int right = 0; right < n; right++) {
sum += arr[right]; // Add the current element to the sum
// Shrink the window from the left if sum exceeds K
while (sum > K) {
sum -= arr[left]; // Subtract the leftmost element from the sum
left++; // Move the left pointer to the right
}
// Update the maximum length if the current window is valid
maxLength = max(maxLength, right - left + 1);
}
return maxLength; // Return the maximum length of the valid subarray
}
int main() {
vector<int> arr = {2, 5, 1, 7, 10}; // Example array
int K = 14; // Example value of K
// Find and print the length of the longest subarray with sum <= K
int result = longestSubarrayWithSum(arr, K);
cout << "The longest subarray length with sum <= " << K << " is: " << result << endl;
return 0;
}
The above code demonstrates the sliding window approach. The key is to balance the window's expansion and contraction to ensure that the sum of the elements inside the window is always less than or equal to K.
This method is much more efficient than the brute-force approach and is commonly used in problems involving subarrays or substrings with specific conditions.
🅱️ Counting the Number of subarrays with a given Sum
In some sliding window problems, the task is not just to find the minimum or maximum length of a subarray, but to count the number of subarrays that satisfy a particular condition. This editorial focuses on such problems, where the goal is to determine the number of subarrays with a given sum, specifically for binary arrays.
Consider the problem of counting the number of subarrays that sum up to 'k'. The approach involves calculating the number of subarrays with at most K ones and then subtracting the number of subarrays with at most K-1 ones. The difference gives the number of subarrays with exactly K ones.
Method
- Define a helper function that counts the number of subarrays with at most K ones. If K is less than 0, the result is 0.
- Iterate through the array using two pointers. Adjust the window size to ensure the sum of the window is at most K. Incrementally add the number of valid subarrays to the result.
- Subtract the result of atMost(K-1) from atMost(K) to get the number of subarrays with exactly K ones.
Code:
#include<bits/stdc++.h>
using namespace std;
class Solution {
public:
// Function to find the number of subarrays with exactly sum S
int numSubarraysWithSum(vector<int>& A, int S) {
return atMost(A, S) - atMost(A, S - 1);
}
private:
// Helper function to find the number of subarrays with at most sum S
int atMost(vector<int>& A, int S) {
if (S < 0) return 0;
int res = 0, i = 0;
// Sliding window approach to count subarrays
for (int j = 0; j < A.size(); j++) {
// Include A[j] in the current window
S -= A[j];
while (S < 0) {
// Shrink the window if the sum exceeds S
S += A[i++];
}
// Count all subarrays ending at j
res += j - i + 1;
}
return res;
}
};
int main() {
Solution sol;
vector<int> A = {1, 0, 1, 0, 1}; // Example array
int S = 2; // Desired sum
int result = sol.numSubarraysWithSum(A, S);
cout << "Number of subarrays with sum " << S << ": " << result << endl;
return 0;
}
By leveraging the difference between the number of subarrays with at most K ones and those with at most K-1 ones, it is possible to efficiently calculate the number of subarrays with exactly K ones. This method provides a concise and powerful solution to a class of sliding window problems.