Sliding Window Pattern

Sliding window avoids redundant computation when processing a contiguous subarray or substring. Instead of recomputing the entire window, we incrementally add the new element and remove the old one.

When to use it

Find max/min/sum in a subarray of fixed size
Find the smallest/longest subarray/substring satisfying a condition
Anything involving "contiguous" elements with a constraint

Template 1: Fixed-size window

// Maximum sum subarray of size k
public int maxSumFixed(int[] nums, int k) {
    int windowSum = 0;
    for (int i = 0; i < k; i++) windowSum += nums[i]; // initial window

    int maxSum = windowSum;
    for (int i = k; i < nums.length; i++) {
        windowSum += nums[i] - nums[i - k]; // slide: add new, remove old
        maxSum = Math.max(maxSum, windowSum);
    }
    return maxSum;
}

Template 2: Variable-size window (expand right, shrink left)

// Longest substring with at most k distinct characters
public int longestSubstringKDistinct(String s, int k) {
    Map<Character, Integer> freq = new HashMap<>();
    int left = 0, maxLen = 0;

    for (int right = 0; right < s.length(); right++) {
        // Expand window
        freq.merge(s.charAt(right), 1, Integer::sum);

        // Shrink window if constraint violated
        while (freq.size() > k) {
            char c = s.charAt(left);
            freq.merge(c, -1, Integer::sum);
            if (freq.get(c) == 0) freq.remove(c);
            left++;
        }

        maxLen = Math.max(maxLen, right - left + 1);
    }
    return maxLen;
}

Classic Problems

Problem	Window Type	Key Data Structure
Max sum subarray of size k	Fixed	Running sum
Longest substring without repeating	Variable	HashMap (last seen index)
Minimum window substring	Variable	HashMap (char counts)
Fruits into baskets	Variable	HashMap (fruit → count)
Max consecutive ones III	Variable	Count of zeros in window

The variable window pattern in words

Expand right pointer — include new element
Check constraint — if violated, shrink left pointer until valid
Record max/min window size

Interview Tip

The variable window pattern is the most common. The key decision: what is the constraint? Once you identify it (distinct chars ≤ k, no duplicates, sum ≤ target), the template is the same.

Sliding Window Pattern

Sliding window avoids redundant computation when processing a contiguous subarray or substring. Instead of recomputing the entire window, we incrementally add the new element and remove the old one.

When to use it

Find max/min/sum in a subarray of fixed size

Find the smallest/longest subarray/substring satisfying a condition

Anything involving "contiguous" elements with a constraint

Template 1: Fixed-size window

// Maximum sum subarray of size k
public int maxSumFixed(int[] nums, int k) {
    int windowSum = 0;
    for (int i = 0; i < k; i++) windowSum += nums[i]; // initial window

    int maxSum = windowSum;
    for (int i = k; i < nums.length; i++) {
        windowSum += nums[i] - nums[i - k]; // slide: add new, remove old
        maxSum = Math.max(maxSum, windowSum);
    }
    return maxSum;
}

Template 2: Variable-size window (expand right, shrink left)

// Longest substring with at most k distinct characters
public int longestSubstringKDistinct(String s, int k) {
    Map<Character, Integer> freq = new HashMap<>();
    int left = 0, maxLen = 0;

    for (int right = 0; right < s.length(); right++) {
        // Expand window
        freq.merge(s.charAt(right), 1, Integer::sum);

        // Shrink window if constraint violated
        while (freq.size() > k) {
            char c = s.charAt(left);
            freq.merge(c, -1, Integer::sum);
            if (freq.get(c) == 0) freq.remove(c);
            left++;
        }

        maxLen = Math.max(maxLen, right - left + 1);
    }
    return maxLen;
}

Classic Problems

Problem	Window Type	Key Data Structure
Max sum subarray of size k	Fixed	Running sum
Longest substring without repeating	Variable	HashMap (last seen index)
Minimum window substring	Variable	HashMap (char counts)
Fruits into baskets	Variable	HashMap (fruit → count)
Max consecutive ones III	Variable	Count of zeros in window

The variable window pattern in words

Expand right pointer — include new element

Check constraint — if violated, shrink left pointer until valid

Record max/min window size

Interview Tip

The variable window pattern is the most common. The key decision: what is the constraint? Once you identify it (distinct chars ≤ k, no duplicates, sum ≤ target), the template is the same.