Sliding Window

The Sliding Window pattern is a technique used to perform operations on a specific window size of a given array or linked list. The window moves across the data structure, expanding and shrinking depending on specific conditions.

This pattern is highly effective for problems asking for the "longest/shortest substring", "maximum/minimum subarray", or finding a specific sequence.

1. Maximum Average Subarray I

Problem: You are given an integer array nums consisting of n elements, and an integer k. Find a contiguous subarray whose length is equal to k that has the maximum average value and return this value.

Approach: Use a fixed-size sliding window of size k. First, calculate the sum of the first k elements. Then, slide the window by adding the next element and subtracting the first element of the previous window.

const findMaxAverage = function(nums, k) {
    let sum = 0;
    for (let i = 0; i < k; i++) {
        sum += nums[i];
    }
    
    let maxSum = sum;
    for (let i = k; i < nums.length; i++) {
        sum += nums[i] - nums[i - k];
        maxSum = Math.max(maxSum, sum);
    }
    
    return maxSum / k;
};

Time Complexity: O(N)
Space Complexity: O(1)

2. Minimum Size Subarray Sum

Problem: Given an array of positive integers nums and a positive integer target, return the minimal length of a contiguous subarray of which the sum is greater than or equal to target. If there is no such subarray, return 0 instead.

Approach: Use a variable-size sliding window. Expand the window from the right until the sum is $\ge$ target. Then, shrink the window from the left to find the minimal length while the sum remains $\ge$ target.

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

Time Complexity: O(N)
Space Complexity: O(1)

3. Longest Substring Without Repeating Characters

Problem: Given a string s, find the length of the longest substring without repeating characters.

Approach: Use a variable sliding window and a Set to track unique characters. If a character is already in the set, remove characters from the left until the duplicate is removed.

const lengthOfLongestSubstring = function(s) {
    let charSet = new Set();
    let left = 0;
    let maxLen = 0;
    
    for (let right = 0; right < s.length; right++) {
        while (charSet.has(s[right])) {
            charSet.delete(s[left]);
            left++;
        }
        charSet.add(s[right]);
        maxLen = Math.max(maxLen, right - left + 1);
    }
    
    return maxLen;
};

Time Complexity: O(N)
Space Complexity: O(min(N, M)) where M is character set size.

4. Fruit Into Baskets

Problem: You only have two baskets, and each basket can only hold a single type of fruit. What is the maximum number of fruits you can pick?

Approach: This translates to: "Find the longest subarray with at most 2 distinct elements." Use a sliding window and a Map to track the frequency of each fruit type. Shrink the window when the Map size exceeds 2.

const totalFruit = function(fruits) {
    let fruitMap = new Map();
    let left = 0, maxFruits = 0;
    
    for (let right = 0; right < fruits.length; right++) {
        fruitMap.set(fruits[right], (fruitMap.get(fruits[right]) || 0) + 1);
        
        while (fruitMap.size > 2) {
            let count = fruitMap.get(fruits[left]);
            if (count === 1) {
                fruitMap.delete(fruits[left]);
            } else {
                fruitMap.set(fruits[left], count - 1);
            }
            left++;
        }
        
        maxFruits = Math.max(maxFruits, right - left + 1);
    }
    
    return maxFruits;
};

Time Complexity: O(N)
Space Complexity: O(1) (Map holds max 3 elements)

5. Longest Repeating Character Replacement

Problem: You are given a string s and an integer k. You can choose any character of the string and change it to any other uppercase English character at most k times. Return the length of the longest substring containing the same letter you can get.

Approach: Keep track of the frequency of characters in the current window. The window is valid if (length of window) - (count of most frequent character) <= k.

const characterReplacement = function(s, k) {
    let counts = new Array(26).fill(0);
    let left = 0, maxLen = 0, maxFreq = 0;
    
    for (let right = 0; right < s.length; right++) {
        let charIdx = s.charCodeAt(right) - 65;
        counts[charIdx]++;
        maxFreq = Math.max(maxFreq, counts[charIdx]);
        
        // If remaining characters to replace exceed k, shrink window
        if ((right - left + 1) - maxFreq > k) {
            counts[s.charCodeAt(left) - 65]--;
            left++;
        }
        
        maxLen = Math.max(maxLen, right - left + 1);
    }
    
    return maxLen;
};

Time Complexity: O(N)
Space Complexity: O(1)

6. Minimum Window Substring

Problem: Given two strings s and t, return the minimum window substring of s such that every character in t (including duplicates) is included in the window.

Approach:

Create a frequency map for t.
Expand right pointer to find a valid window that satisfies all character counts.
Shrink left pointer to minimize the window size while it remains valid.

const minWindow = function(s, t) {
    if (t.length > s.length) return "";
    
    let tMap = new Map();
    for (let char of t) {
        tMap.set(char, (tMap.get(char) || 0) + 1);
    }
    
    let left = 0, right = 0;
    let required = tMap.size;
    let formed = 0;
    let windowCounts = new Map();
    let minLen = Infinity;
    let minLeft = 0;
    
    while (right < s.length) {
        let char = s[right];
        windowCounts.set(char, (windowCounts.get(char) || 0) + 1);
        
        if (tMap.has(char) && windowCounts.get(char) === tMap.get(char)) {
            formed++;
        }
        
        while (left <= right && formed === required) {
            char = s[left];
            if (right - left + 1 < minLen) {
                minLen = right - left + 1;
                minLeft = left;
            }
            
            windowCounts.set(char, windowCounts.get(char) - 1);
            if (tMap.has(char) && windowCounts.get(char) < tMap.get(char)) {
                formed--;
            }
            left++;
        }
        right++;
    }
    
    return minLen === Infinity ? "" : s.substring(minLeft, minLeft + minLen);
};

Time Complexity: O(S + T)
Space Complexity: O(S + T)

7. Sliding Window Maximum

Problem: You are given an array of integers nums, there is a sliding window of size k which is moving from the very left of the array to the very right. Return the max sliding window.

Approach: Use a Monotonic Deque (double-ended queue). We store the indices of elements. We ensure the deque only contains indices of elements in descending order of their values. The front of the deque will always be the maximum for the current window.

const maxSlidingWindow = function(nums, k) {
    let res = [];
    let deque = []; // Stores indices
    
    for (let i = 0; i < nums.length; i++) {
        // Remove indices that are out of bounds of the current window
        if (deque.length > 0 && deque[0] === i - k) {
            deque.shift();
        }
        
        // Remove elements smaller than the current element from the back
        while (deque.length > 0 && nums[deque[deque.length - 1]] < nums[i]) {
            deque.pop();
        }
        
        deque.push(i);
        
        // Once we hit the first window size k, add the max to the result
        if (i >= k - 1) {
            res.push(nums[deque[0]]);
        }
    }
    
    return res;
};

Time Complexity: O(N)
Space Complexity: O(K)

Fast and Slow Pointers Merge Intervals