Sliding Window Algorithm Explained
The sliding window algorithm is a powerful technique used to solve problems involving subarrays or substrings of a specific size. Instead of repeatedly iterating through all possible subarrays or substrings, it efficiently "slides" a window of a fixed size across the data structure, performing computations only on the elements within the window.
Algorithm
The general idea behind the sliding window algorithm involves these steps:
- Define the Window: Determine the size (k) of the window you need to consider.
- Initialize the Window: Create an initial window of size k, usually starting from the beginning of the array or string.
- Perform Operations: Calculate the desired value (e.g., sum, maximum, count) within the current window.
- Slide the Window: Move the window one element to the right. This typically involves:
- Removing the element that just left the window (the leftmost element).
- Adding the new element that just entered the window (the rightmost element).
- Repeat: Continue steps 3 and 4 until the window reaches the end of the data structure.
- Store Results: Keep track of the results obtained for each window position.
Mathematics
The mathematics involved in the sliding window algorithm often depends on the specific problem you are trying to solve. However, some fundamental mathematical concepts are frequently used:
- Summation: For problems involving the sum of elements in a window, you'll be dealing with sums of consecutive elements. If $W_i$ represents the window at position $i$, containing elements $a_i, a_{i+1}, ..., a_{i+k-1}$, the sum $S_i$ is given by: $S_i = \sum_{j=i}^{i+k-1} a_j = a_i + a_{i+1} + ... + a_{i+k-1}$ When the window slides to $W_{i+1}$ (elements $a_{i+1}, a_{i+2}, ..., a_{i+k}$), the new sum $S_{i+1}$ can be efficiently calculated using the previous sum: $S_{i+1} = S_i - a_i + a_{i+k}$ This avoids recalculating the sum of $k$ elements in each step.
- Counting: For problems involving counting occurrences of certain elements within a window, you might use frequency maps or counters. When the window slides, you decrement the count of the element leaving the window and increment the count of the element entering.
- Maximum/Minimum: Finding the maximum or minimum element within a sliding window can be done naively by iterating through the window in each step. However, more efficient techniques using data structures like dequeues can maintain the maximum or minimum in $O(1)$ average time per slide.
Time and Memory Complexity
- Time Complexity: In most cases, the sliding window algorithm iterates through the input array or string only once. The operations performed within each window (addition, subtraction, comparison, hash map updates) usually take constant time or logarithmic time (if using balanced trees or heaps for maintaining maximum/minimum). Therefore, the overall time complexity is often linear, i.e., $O(n)$, where $n$ is the size of the input.
- Memory Complexity: The memory complexity depends on the information you need to store for each window. For simple problems like finding the maximum sum, the memory usage is typically constant, $O(1)$. However, if you need to store frequencies of elements within the window (e.g., using a hash map), the memory complexity might be proportional to the size of the window in the worst case, i.e., $O(k)$, where $k$ is the window size, or the number of distinct elements in the input if that's the limiting factor.
Easy Problems
Problem 1: Maximum Sum Subarray of Size K (Codeforces)
Problem Statement (Hypothetical): Given an array of integers and an integer $k$, find the maximum sum of any contiguous subarray of size $k$.
Input Example:
array = [1, 4, 2, 10, 2, 3, 1, 0, 20]
k = 4
Output Example:
24 (from subarray [2, 10, 2, 3])
C++ Code:
#include
#include
#include
#include
int main() {
std::vector arr = {1, 4, 2, 10, 2, 3, 1, 0, 20};
int k = 4;
int n = arr.size();
if (k > n) {
std::cout << "Invalid value of k" << std::endl;
return 1;
}
int windowSum = std::accumulate(arr.begin(), arr.begin() + k, 0);
int maxSum = windowSum;
for (int i = k; i < n; ++i) {
windowSum = windowSum - arr[i - k] + arr[i];
maxSum = std::max(maxSum, windowSum);
}
std::cout << maxSum << std::endl;
return 0;
}
Problem 2: Count Occurrences of Anagrams (Hypothetical)
Problem Statement (Hypothetical): Given a string `text` and a string `pattern`, find the number of occurrences of `pattern`'s anagrams within `text`. Assume both strings contain only lowercase English letters.
Input Example:
text = "cbaebabacd"
pattern = "abc"
Output Example:
2 (occurrences at index 0 "cba" and index 6 "bac")
C++ Code:
#include
#include
#include
#include
bool areAnagrams(const std::string& s1, const std::string& s2) {
if (s1.length() != s2.length()) {
return false;
}
std::string sortedS1 = s1;
std::string sortedS2 = s2;
std::sort(sortedS1.begin(), sortedS1.end());
std::sort(sortedS2.begin(), sortedS2.end());
return sortedS1 == sortedS2;
}
int main() {
std::string text = "cbaebabacd";
std::string pattern = "abc";
int n = text.length();
int m = pattern.length();
int count = 0;
if (m > n) {
std::cout << 0 << std::endl;
return 0;
}
for (int i = 0; i <= n - m; ++i) {
std::string sub = text.substr(i, m);
if (areAnagrams(sub, pattern)) {
count++;
}
}
std::cout << count << std::endl;
return 0;
}
Intermediate Problems
Problem 3: Minimum Size Subarray Sum (Codeforces - Variation)
Problem Statement (Variation): Given an array of positive integers and a target sum $S$, find the minimum length of a contiguous subarray whose sum is greater than or equal to $S$. If there is no such subarray, return 0.
Input Example:
array = [2, 3, 1, 2, 4, 3]
targetSum = 7
Output Example:
2 (subarray [4, 3] has sum 7 and length 2)
C++ Code:
#include
#include
#include
int main() {
std::vector arr = {2, 3, 1, 2, 4, 3};
int targetSum = 7;
int n = arr.size();
int minLength = n + 1;
int windowSum = 0;
int windowStart = 0;
for (int windowEnd = 0; windowEnd < n; ++windowEnd) {
windowSum += arr[windowEnd];
while (windowSum >= targetSum) {
minLength = std::min(minLength, windowEnd - windowStart + 1);
windowSum -= arr[windowStart];
windowStart++;
}
}
if (minLength > n) {
std::cout << 0 << std::endl;
} else {
std::cout << minLength << std::endl;
}
return 0;
}
Problem 4: Longest Substring Without Repeating Characters (Conceptual Adaptation)
Problem Statement (Conceptual Adaptation): Given a string `s`, find the length of the longest substring without repeating characters.
Input Example:
s = "abcabcbb"
Output Example:
3 ("abc" has length 3)
C++ Code:
#include
#include
#include
#include
int main() {
std::string s = "abcabcbb";
int n = s.length();
int maxLength = 0;
int windowStart = 0;
std::unordered_map charIndexMap;
for (int windowEnd = 0; windowEnd < n; ++windowEnd) {
char currentChar = s[windowEnd];
if (charIndexMap.count(currentChar) && charIndexMap[currentChar] >= windowStart) {
windowStart = charIndexMap[currentChar] + 1;
}
charIndexMap[currentChar] = windowEnd;
maxLength = std::max(maxLength, windowEnd - windowStart + 1);
}
std::cout << maxLength << std::endl;
return 0;
}
Hard Problem
Problem 5: Minimum Window Substring (Conceptual Adaptation - Harder Variant)
Problem Statement (Conceptual Adaptation - Harder Variant): Given two strings `s` and `t`, find the shortest substring in `s` that contains all the characters in `t` (including duplicates). If no such substring exists, return an empty string.
Input Example:
s = "ADOBECODEBANC"
t = "ABC"
Output Example:
"BANC"
C++ Code:
#include
#include
#include
#include
int main() {
std::string s = "ADOBECODEBANC";
std::string t = "ABC";
int n = s.length();
int m = t.length();
if (m > n || m == 0) {
std::cout << "" << std::endl;
return 0;
}
std::unordered_map targetMap;
for (char c : t) {
targetMap[c]++;
}
int windowStart = 0;
int minLength = n + 1;
int head = 0;
int formed = 0;
std::unordered_map windowMap;
for (int windowEnd = 0; windowEnd < n; ++windowEnd) {
char currentChar = s[windowEnd];
windowMap[currentChar]++;
if (targetMap.count(currentChar) && windowMap[currentChar] <= targetMap[currentChar]) {
formed++;
}
while (formed == m) {
if (windowEnd - windowStart + 1 < minLength) {
minLength = windowEnd - windowStart + 1;
head = windowStart;
}
char startChar = s[windowStart];
windowMap[startChar]--;
if (targetMap.count(startChar) && windowMap[startChar] < targetMap[startChar]) {
formed--;
}
windowStart++;
}
}
if (minLength > n) {
std::cout << "" << std::endl;
} else {
std::cout << s.substr(head, minLength) << std::endl;
}
return 0;
}