Master problems involving subarrays, substrings, or variable-length windows using this powerful pattern.
When the problem requires a subarray/substring of size k
When the window can grow/shrink depending on the condition
Finding longest, shortest, or maximum sum windows
When processing continuous streams of data
Usually O(n), efficient for continuous data
O(1) to O(n), depending on storage
Incorrectly shrinking or expanding the window
Think in terms of window size & boundary conditions
Find the maximum sum of k consecutive elements
function maxSum(arr: number[], k: number): number {
let maxSum = 0, windowSum = 0;
for (let i = 0; i < k; i++) {
windowSum += arr[i];
}
maxSum = windowSum;
for (let i = k; i < arr.length; i++) {
windowSum += arr[i] - arr[i - k];
maxSum = Math.max(maxSum, windowSum);
}
return maxSum;
}Dynamic sliding window to find minimal length subarray with sum ≥ target
function minSubArrayLen(target: number, nums: number[]): number {
let left = 0, sum = 0, minLen = Infinity;
for (let right = 0; right < nums.length; right++) {
sum += nums[right];
while (sum >= target) {
minLen = Math.min(minLen, right - left + 1);
sum -= nums[left++];
}
}
return minLen === Infinity ? 0 : minLen;
}Dynamic-size sliding window for string processing
function lengthOfLongestSubstring(s: string): number {
let seen = new Map<string, number>();
let left = 0, maxLen = 0;
for (let right = 0; right < s.length; right++) {
const char = s[right];
if (seen.has(char) && seen.get(char)! >= left) {
left = seen.get(char)! + 1;
}
seen.set(char, right);
maxLen = Math.max(maxLen, right - left + 1);
}
return maxLen;
}Maximum Sum Subarray of Size K
easyLongest Substring Without Repeating Characters
mediumMinimum Window Substring
hardLongest Substring with At Most K Distinct Characters
mediumSliding Window Maximum
hard