This article provides a concise summary of sliding window templates followed by practical examples. The recommended reading approach: skim the summary first, then study how each template is applied in the examples, and finally revisit the summary to solidify your understanding.

Summary

Problems that are well-suited for the sliding window technique share a common prerequisite: they involve contiguous subarrays, substrings, or subsequences. The key is continuity.

Follow these four steps:

Step 1: Define the variables to maintain (for sliding window problems, these are often minimum length, maximum length, or a hashmap/frequency table).

Step 2: Define the start and end boundaries of the window, then slide the window.

• start = 0
• end is typically the loop variable i in a for loop.

Step 3: Update the variables that need to be maintained. Some variables may require an if statement (e.g., tracking the maximum or minimum length).

Step 4 - Case 1: Fixed window length. Use an if condition to check whether the current window length has reached the required size. If it has, move the left pointer forward by one to keep the window length constant, but before moving it, update the (partial or all) variables defined in Step 1.

Step 4 - Case 2: Varible window length. Use a while loop to shrink the window from the left whenever it becomes invalid. Update the maintained variables before each left move until the window becomes valid again.

Step 5: Return the result.

function slidingWindowTemplate(s) {
    // Step 1: Define variables to maintain (e.g., maxLength, hashmap)
    let maxLen = 0;
    let freq = new Map();

    // Step 2: Define window boundaries
    let start = 0;
    for (let end = 0; end < s.length; end++) {
        // Step 3: Update variables as the right boundary expands
        // ... update freq, compute new values ...

        // -------------------------------------------------
        // Choose the appropriate case below based on the problem
        // -------------------------------------------------

        // Case 1: Fixed window size
        if (end - start + 1 === k) {
            // Update variables before moving start
            // ...
            start++;
        }

        // Case 2: Variable window size – shrink while invalid
        while (/* invalid condition */) {
            // Update variables (e.g., adjust frequency map)
            // ...
            start++;
        }
    }

    // Step 5: Return the answer
    return maxLen;
}

Example 1: Maximum Average Subarray I (LeetCode 643)

Given an integer array nums consisting of n elements and an integer k, find the contiguous subarray of length k that has the maximum average value and return that value.

Essential, we maintain the sum inside a sliding window of length k. The right pointer expands to explore, and the left pointer advances to keep the window length fixed.

function findMaxAverage(nums, k) {
    // Step 1: Maintain maxSum and current window sum
    let maxSum = -Infinity;
    let currentSum = 0;

    // Step 2: Define window boundaries
    let windowStart = 0;
    for (let windowEnd = 0; windowEnd < nums.length; windowEnd++) {
        // Step 3: Expand – add the incoming element
        currentSum += nums[windowEnd];

        // Step 4 – Case 1: Fixed window size
        if (windowEnd - windowStart + 1 === k) {
            // Update maxSum before moving the start pointer
            maxSum = Math.max(maxSum, currentSum);
            // Remove the outgoing element and slide the window
            currentSum -= nums[windowStart];
            windowStart++;
        }
    }

    // Step 5: Return the maximum average
    return maxSum / k;
}

Example 2: Longest Substring Without Repeating Characters (LeetCode 3)

Find the length of the longest substring without repeating characters. The window must be contiguous. The right pointer expands to seek a longer length, and the left pointer advances to remove duplicates, keeping the window valid.

function lengthOfLongestSubstring(s) {
    // Step 1: Maintain max length and a frequency map
    let maxLen = 0;
    let charCount = new Map();

    // Step 2: Define window boundaries
    let start = 0;
    for (let end = 0; end < s.length; end++) {
        // Step 3: Expand – add current character to the map
        let currentChar = s[end];
        charCount.set(currentChar, (charCount.get(currentChar) || 0) + 1);

        // If all characters in the window are unique,
        // charCount.size equals the window length
        if (end - start + 1 === charCount.size) {
            maxLen = Math.max(maxLen, end - start + 1);
        }

        // Step 4 – Case 2: Shrink while duplicate characters exist
        while (end - start + 1 > charCount.size) {
            let leftChar = s[start];
            let count = charCount.get(leftChar);
            if (count === 1) {
                charCount.delete(leftChar);
            } else {
                charCount.set(leftChar, count - 1);
            }
            start++;
        }

        // The window is now guaranteed valid, update maxLen
        maxLen = Math.max(maxLen, end - start + 1);
    }

    // Step 5: Return result
    return maxLen;
}

Example 3: Minimum Size Subarray Sum (LeetCode 209)

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

The right pointer expands to increase the sum, and the left pointer shrinks the window to find the minimal length whenever the sum ≥ target.

function minSubArrayLen(target, nums) {
    // Step 1: Maintain minimal length and current sum
    let minLength = Infinity;
    let currentSum = 0;

    // Step 2: Define window boundaries
    let left = 0;
    for (let right = 0; right < nums.length; right++) {
        // Step 3: Expand – add current element
        currentSum += nums[right];

        // Step 4 – Case 2: Shrink while condition is satisfied
        while (currentSum >= target) {
            // Update minimal length using current window size
            minLength = Math.min(minLength, right - left + 1);
            // Remove the leftmost element and move left pointer
            currentSum -= nums[left];
            left++;
        }
    }

    // Step 5: Return 0 if no valid subarray was found
    return minLength === Infinity ? 0 : minLength;
}