Sliding Window Pattern

1. Fixed-size Window Techniques

Technique	Pattern	Use Case	Time
Fixed Window	`sum = arr[0...k-1]; slide right`	Calculate sum/avg of k consecutive elements	`O(n)`
Sliding Average	`avg = sum / k`	Moving average calculations, smoothing data	`O(n)`
Window Update	`sum += arr[i] - arr[i-k]`	Add new element, remove old element	`O(1)`
Max in Window	`deque for max tracking`	Maximum element in each window of size k	`O(n)`

Example: Maximum sum of k consecutive elements

function maxSumFixedWindow(arr, k) {
    if (arr.length < k) return null;
    
    // Calculate first window sum
    let windowSum = 0;
    for (let i = 0; i < k; i++) {
        windowSum += arr[i];
    }
    
    let maxSum = windowSum;
    
    // Slide window: add next, remove first
    for (let i = k; i < arr.length; i++) {
        windowSum += arr[i] - arr[i - k];
        maxSum = Math.max(maxSum, windowSum);
    }
    
    return maxSum;
}

// Example usage
const arr = [2, 1, 5, 1, 3, 2];
console.log(maxSumFixedWindow(arr, 3)); // Output: 9 (5+1+3)

2. Variable-size Window Optimization

Pattern	Strategy	When to Use	Complexity
Expand-Shrink	Expand right until condition fails, then shrink left	Find smallest/largest window meeting criteria	`O(n)`
Two Pointer	Left and right pointers move independently	Subarray sum equals target, substring problems	`O(n)`
HashMap Tracking	Track frequency/count in current window	Distinct elements, character frequency	`O(n)`
Condition Check	Validate window on each expansion/shrink	Complex constraints validation	`O(n)`

Example: Smallest subarray with sum ≥ target

function minSubArrayLen(target, nums) {
    let left = 0, sum = 0;
    let minLen = Infinity;
    
    for (let right = 0; right < nums.length; right++) {
        sum += nums[right]; // Expand window
        
        // Shrink window while condition met
        while (sum >= target) {
            minLen = Math.min(minLen, right - left + 1);
            sum -= nums[left];
            left++;
        }
    }
    
    return minLen === Infinity ? 0 : minLen;
}

// Example
console.log(minSubArrayLen(7, [2,3,1,2,4,3])); // Output: 2 ([4,3])

3. Maximum/Minimum Subarray Problems

Problem Type	Approach	Data Structure	Example
Max Sum Subarray	Kadane's algorithm or sliding window	Variables for current/max sum	Maximum profit, maximum subarray sum
Min/Max in Window	Monotonic deque	Deque storing indices	Sliding window maximum/minimum
Product Maximum	Track both max and min (negative numbers)	Two variables for max/min product	Maximum product subarray
Fixed Length Max	Fixed window with running max/min	Window sum + comparison	Max average subarray of length k

Example: Sliding Window Maximum

function maxSlidingWindow(nums, k) {
    const result = [];
    const deque = []; // Store indices
    
    for (let i = 0; i < nums.length; i++) {
        // Remove indices outside window
        while (deque.length && 
               deque[0] <= i - k) {
            deque.shift();
        }
        
        // Remove smaller elements
        while (deque.length && 
               nums[deque[deque.length-1]] < nums[i]) {
            deque.pop();
        }
        
        deque.push(i);
        
        if (i >= k - 1) {
            result.push(nums[deque[0]]);
        }
    }
    
    return result;
}

Example: Maximum Product Subarray

function maxProduct(nums) {
    let maxProd = nums[0];
    let curMax = nums[0];
    let curMin = nums[0];
    
    for (let i = 1; i < nums.length; i++) {
        const num = nums[i];
        
        // Swap if negative
        if (num < 0) {
            [curMax, curMin] = [curMin, curMax];
        }
        
        curMax = Math.max(num, curMax * num);
        curMin = Math.min(num, curMin * num);
        
        maxProd = Math.max(maxProd, curMax);
    }
    
    return maxProd;
}

4. Longest Substring Without Repeating Characters

Pattern	Key Technique	Tracking Method	Common Problems
Unique Characters	HashMap/Set for character tracking	Store last seen index of each character	Longest substring without repeating chars
K Distinct Elements	Expand until k+1 distinct, then shrink	HashMap with character frequency	Longest substring with k distinct chars
Character Replacement	Track most frequent + replacement count	Frequency map + max frequency variable	Longest repeating char replacement
Anagram Window	Character frequency matching	Two frequency maps comparison	Find all anagrams in string

Example: Longest substring without repeating characters

function lengthOfLongestSubstring(s) {
    const charMap = new Map();
    let left = 0, maxLen = 0;
    
    for (let right = 0; right < s.length; right++) {
        const char = s[right];
        
        // If duplicate found, move left pointer
        if (charMap.has(char)) {
            left = Math.max(left, charMap.get(char) + 1);
        }
        
        charMap.set(char, right);
        maxLen = Math.max(maxLen, right - left + 1);
    }
    
    return maxLen;
}

// Example
console.log(lengthOfLongestSubstring("abcabcbb")); // Output: 3 ("abc")

Example: Longest substring with k distinct characters

function lengthOfLongestSubstringKDistinct(s, k) {
    const charCount = new Map();
    let left = 0, maxLen = 0;
    
    for (let right = 0; right < s.length; right++) {
        const char = s[right];
        charCount.set(char, (charCount.get(char) || 0) + 1);
        
        // Shrink window if more than k distinct
        while (charCount.size > k) {
            const leftChar = s[left];
            charCount.set(leftChar, charCount.get(leftChar) - 1);
            if (charCount.get(leftChar) === 0) {
                charCount.delete(leftChar);
            }
            left++;
        }
        
        maxLen = Math.max(maxLen, right - left + 1);
    }
    
    return maxLen;
}

5. Two-pointer Sliding Window Hybrid Approach

Variant	Pointer Movement	Use Case	Key Insight
Same Direction	Both pointers move left to right	Variable window size problems	Window expands/shrinks dynamically
Opposite Direction	Left moves right, right moves left	Palindrome check, two sum in sorted array	Converge towards middle or target
Fast-Slow Pattern	One pointer moves faster than other	Cycle detection, middle element	Speed differential reveals patterns
Partitioning	One pointer scans, other marks boundary	Dutch national flag, partition array	Maintain invariant between pointers

Example: Container with most water (opposite direction)

function maxArea(height) {
    let left = 0, right = height.length - 1;
    let maxArea = 0;
    
    while (left < right) {
        const width = right - left;
        const minHeight = Math.min(height[left], height[right]);
        const area = width * minHeight;
        maxArea = Math.max(maxArea, area);
        
        // Move pointer with smaller height
        if (height[left] < height[right]) {
            left++;
        } else {
            right--;
        }
    }
    
    return maxArea;
}

6. Time Complexity O(n) Analysis

Aspect	Analysis	Explanation
Single Pass	`O(n)`	Each element visited at most once by right pointer
Left Pointer Movement	`O(n) total`	Left pointer moves at most n times across entire execution
Combined Movement	`O(2n) = O(n)`	Both pointers together traverse array once
Space Complexity	`O(1) to O(k)`	O(1) for counters, O(k) for HashMap with k unique elements

Note: Sliding window achieves O(n) time by ensuring each element is processed at most twice - once when entering window (right pointer) and once when leaving (left pointer). This is superior to naive nested loops O(n²).

Sliding Window Pattern Summary

Fixed Window: Calculate initial sum, slide by adding/removing elements
Variable Window: Expand until condition breaks, shrink until valid
Template: Use HashMap for tracking, two pointers for boundaries
Optimization: Amortized O(n) - each element touched maximum twice
Common Mistakes: Off-by-one errors, not updating window state correctly

Warning: Always verify window validity before updating result. Ensure left pointer doesn't exceed right pointer. Handle edge cases: empty array, k > array length, negative numbers in product problems.

Related Cheat Sheets

Datastructures Algorithms