Sliding Window Patterns: Fixed, Variable, and Two Pointer Variants

The sliding window technique transforms brute-force O(n^2) solutions into O(n) by maintaining a window of elements and sliding it across the input. It applies whenever you need to find a contiguous subarray or substring that satisfies some condition. This guide covers every variant with templates and classic problem solutions.

When to Use Sliding Window

Look for these signals in the problem statement:

• “contiguous subarray” or “substring”
• “maximum/minimum length” of a subarray
• “at most k distinct” elements
• “sum equals/exceeds target”

Pattern 1: Fixed-Size Window

The window size is given. Slide it one element at a time, adding the new element and removing the old one.

Array: [2, 1, 5, 1, 3, 2]   Window size k=3

Step 1: [2, 1, 5] 1, 3, 2    sum=8
Step 2:  2 [1, 5, 1] 3, 2    sum=7
Step 3:  2, 1 [5, 1, 3] 2    sum=9  <-- max
Step 4:  2, 1, 5 [1, 3, 2]   sum=6

Template

def fixed_window(arr, k):
    """Template for fixed-size sliding window."""
    n = len(arr)
    if n < k:
        return None
    
    # Build initial window
    window_sum = sum(arr[:k])
    result = window_sum
    
    # Slide the window
    for i in range(k, n):
        window_sum += arr[i] - arr[i - k]  # add new, remove old
        result = max(result, window_sum)     # update result
    
    return result

Problem: Maximum Average Subarray (LC 643)

Find the contiguous subarray of length k with the maximum average.

def findMaxAverage(nums: list[int], k: int) -> float:
    window_sum = sum(nums[:k])
    max_sum = window_sum
    
    for i in range(k, len(nums)):
        window_sum += nums[i] - nums[i - k]
        max_sum = max(max_sum, window_sum)
    
    return max_sum / k

# Example
print(findMaxAverage([1, 12, -5, -6, 50, 3], 4))  # 12.75

Problem: Maximum Sum of Distinct Subarrays (LC 2461)

def maximumSubarraySum(nums: list[int], k: int) -> int:
    seen = {}
    window_sum = 0
    max_sum = 0
    
    for i, num in enumerate(nums):
        window_sum += num
        seen[num] = seen.get(num, 0) + 1
        
        if i >= k:
            old = nums[i - k]
            window_sum -= old
            seen[old] -= 1
            if seen[old] == 0:
                del seen[old]
        
        if i >= k - 1 and len(seen) == k:
            max_sum = max(max_sum, window_sum)
    
    return max_sum

Pattern 2: Variable-Size Window

The window size is not fixed. You expand the right boundary until a condition breaks, then shrink from the left until the condition is restored.

Template

def variable_window(arr, condition_fn):
    """Template for variable-size sliding window."""
    left = 0
    result = 0
    window_state = {}  # track window contents
    
    for right in range(len(arr)):
        # Expand: add arr[right] to window state
        # ...
        
        # Shrink: while window is invalid
        while not condition_fn(window_state):
            # Remove arr[left] from window state
            # ...
            left += 1
        
        # Update result
        result = max(result, right - left + 1)
    
    return result

Problem: Longest Substring Without Repeating Characters (LC 3)

def lengthOfLongestSubstring(s: str) -> int:
    seen = {}
    left = 0
    max_len = 0
    
    for right, char in enumerate(s):
        if char in seen and seen[char] >= left:
            left = seen[char] + 1
        seen[char] = right
        max_len = max(max_len, right - left + 1)
    
    return max_len

# Examples
print(lengthOfLongestSubstring("abcabcbb"))  # 3 ("abc")
print(lengthOfLongestSubstring("bbbbb"))     # 1 ("b")
print(lengthOfLongestSubstring("pwwkew"))    # 3 ("wke")

// Java version
public int lengthOfLongestSubstring(String s) {
    Map<Character, Integer> seen = new HashMap<>();
    int left = 0, maxLen = 0;
    
    for (int right = 0; right < s.length(); right++) {
        char c = s.charAt(right);
        if (seen.containsKey(c) && seen.get(c) >= left) {
            left = seen.get(c) + 1;
        }
        seen.put(c, right);
        maxLen = Math.max(maxLen, right - left + 1);
    }
    return maxLen;
}

Problem: Minimum Size Subarray Sum (LC 209)

Find the minimum length subarray with sum >= target.

def minSubArrayLen(target: int, nums: list[int]) -> int:
    left = 0
    current_sum = 0
    min_len = float('inf')
    
    for right in range(len(nums)):
        current_sum += nums[right]
        
        while current_sum >= target:
            min_len = min(min_len, right - left + 1)
            current_sum -= nums[left]
            left += 1
    
    return min_len if min_len != float('inf') else 0

print(minSubArrayLen(7, [2, 3, 1, 2, 4, 3]))  # 2 ([4,3])

Problem: Longest Substring with At Most K Distinct Characters (LC 340)

def lengthOfLongestSubstringKDistinct(s: str, k: int) -> int:
    if k == 0:
        return 0
    
    char_count = {}
    left = 0
    max_len = 0
    
    for right, char in enumerate(s):
        char_count[char] = char_count.get(char, 0) + 1
        
        while len(char_count) > k:
            left_char = s[left]
            char_count[left_char] -= 1
            if char_count[left_char] == 0:
                del char_count[left_char]
            left += 1
        
        max_len = max(max_len, right - left + 1)
    
    return max_len

print(lengthOfLongestSubstringKDistinct("eceba", 2))   # 3 ("ece")
print(lengthOfLongestSubstringKDistinct("aabacbebebe", 3))  # 7

Pattern 3: Two Pointer Variants

Two pointers start at different positions and move toward each other or in the same direction.

Two Sum on Sorted Array (LC 167)

def twoSum(numbers: list[int], target: int) -> list[int]:
    left, right = 0, len(numbers) - 1
    
    while left < right:
        current_sum = numbers[left] + numbers[right]
        if current_sum == target:
            return [left + 1, right + 1]  # 1-indexed
        elif current_sum < target:
            left += 1
        else:
            right -= 1
    
    return []

print(twoSum([2, 7, 11, 15], 9))  # [1, 2]

Container With Most Water (LC 11)

def maxArea(height: list[int]) -> int:
    left, right = 0, len(height) - 1
    max_water = 0
    
    while left < right:
        width = right - left
        h = min(height[left], height[right])
        max_water = max(max_water, width * h)
        
        # Move the shorter side inward
        if height[left] < height[right]:
            left += 1
        else:
            right -= 1
    
    return max_water

print(maxArea([1, 8, 6, 2, 5, 4, 8, 3, 7]))  # 49

3Sum (LC 15)

def threeSum(nums: list[int]) -> list[list[int]]:
    nums.sort()
    result = []
    
    for i in range(len(nums) - 2):
        if i > 0 and nums[i] == nums[i - 1]:
            continue  # skip duplicates
        
        left, right = i + 1, len(nums) - 1
        while left < right:
            total = nums[i] + nums[left] + nums[right]
            if total == 0:
                result.append([nums[i], nums[left], nums[right]])
                while left < right and nums[left] == nums[left + 1]:
                    left += 1
                while left < right and nums[right] == nums[right - 1]:
                    right -= 1
                left += 1
                right -= 1
            elif total < 0:
                left += 1
            else:
                right -= 1
    
    return result

print(threeSum([-1, 0, 1, 2, -1, -4]))  # [[-1,-1,2],[-1,0,1]]

Pattern 4: Sliding Window with Counter

For problems involving character frequency constraints.

Problem: Minimum Window Substring (LC 76)

Find the minimum window in s that contains all characters of t.

from collections import Counter

def minWindow(s: str, t: str) -> str:
    if not t or not s:
        return ""
    
    need = Counter(t)
    have = {}
    formed = 0
    required = len(need)
    
    left = 0
    min_len = float('inf')
    min_start = 0
    
    for right, char in enumerate(s):
        have[char] = have.get(char, 0) + 1
        
        if char in need and have[char] == need[char]:
            formed += 1
        
        while formed == required:
            # Update result
            if right - left + 1 < min_len:
                min_len = right - left + 1
                min_start = left
            
            # Shrink window
            left_char = s[left]
            have[left_char] -= 1
            if left_char in need and have[left_char] < need[left_char]:
                formed -= 1
            left += 1
    
    return s[min_start:min_start + min_len] if min_len != float('inf') else ""

print(minWindow("ADOBECODEBANC", "ABC"))  # "BANC"

Recognizing the Pattern

Key Takeaways

Fixed windows slide by adding one element and removing one, keeping the window size constant. Variable windows expand the right boundary and shrink the left to maintain a condition. Two pointer variants work on sorted arrays or when you need to converge from both ends. The counter variant handles frequency-based constraints. All sliding window solutions run in O(n) time because each element enters and leaves the window at most once. When you see “contiguous subarray” or “substring” in a problem, think sliding window first.