Introduction to Sliding Window

The sliding window technique is an optimization method for problems involving subarrays or substrings. It transforms problems that would normally require O(n²) time into O(n) solutions.

The Core Idea

Instead of recalculating everything for each subarray, we maintain a "window" that slides through the array, adding new elements and removing old ones.

Think of it like a window sliding across a wall - as it moves right, new things come into view on the right side while things disappear on the left side.

When to Use Sliding Window

Look for these keywords in problems:

• "Contiguous subarray" or "substring"
• "Maximum/minimum/longest" subarray
• "Fixed window size" or "variable window size"
• Words like "consecutive", "contiguous", "in a row"

Two Types of Sliding Windows

1. Fixed-Size Window

The window size is constant.

Example: Maximum sum of subarray of size k

def max_sum_subarray(nums, k):
    if len(nums) < k:
        return 0

    # Calculate first window
    window_sum = sum(nums[:k])
    max_sum = window_sum

    # Slide window
    for i in range(k, len(nums)):
        # Remove leftmost, add rightmost
        window_sum = window_sum - nums[i - k] + nums[i]
        max_sum = max(max_sum, window_sum)

    return max_sum

nums = [1, 3, 2, 5, 1, 4, 2]
print(max_sum_subarray(nums, 3))  # 10 (5 + 1 + 4)

2. Variable-Size Window

The window expands and shrinks based on conditions.

Example: Longest substring without repeating characters

def length_of_longest_substring(s):
    char_set = set()
    left = 0
    max_length = 0

    for right in range(len(s)):
        # Shrink window until no duplicates
        while s[right] in char_set:
            char_set.remove(s[left])
            left += 1

        # Expand window
        char_set.add(s[right])
        max_length = max(max_length, right - left + 1)

    return max_length

print(length_of_longest_substring("abcabcbb"))  # 3 ("abc")

The Pattern Template

Fixed Window

def fixed_window(arr, k):
    # Initialize window
    window_state = initialize()

    # Process first window
    for i in range(k):
        update_state(window_state, arr[i])

    result = calculate_result(window_state)

    # Slide window
    for i in range(k, len(arr)):
        # Remove element leaving window
        remove_from_state(window_state, arr[i - k])

        # Add element entering window
        add_to_state(window_state, arr[i])

        # Update result
        result = update_result(result, window_state)

    return result

Variable Window

def variable_window(arr, condition):
    left = 0
    window_state = initialize()
    result = initialize_result()

    for right in range(len(arr)):
        # Expand window - add right element
        add_to_state(window_state, arr[right])

        # Shrink window while condition violated
        while not valid(window_state, condition):
            remove_from_state(window_state, arr[left])
            left += 1

        # Update result with valid window
        result = update_result(result, right - left + 1)

    return result

Simple Examples

Example 1: Average of Subarrays

def avg_of_subarrays(nums, k):
    result = []
    window_sum = 0

    for i in range(len(nums)):
        window_sum += nums[i]

        if i >= k - 1:
            result.append(window_sum / k)
            window_sum -= nums[i - k + 1]

    return result

nums = [1, 3, 2, 6, -1, 4, 1, 8, 2]
print(avg_of_subarrays(nums, 5))

Example 2: Max Consecutive Ones

def max_consecutive_ones(nums, k):
    """Max 1s if we can flip at most k zeros"""
    left = 0
    zeros = 0
    max_len = 0

    for right in range(len(nums)):
        if nums[right] == 0:
            zeros += 1

        # Shrink if too many zeros
        while zeros > k:
            if nums[left] == 0:
                zeros -= 1
            left += 1

        max_len = max(max_len, right - left + 1)

    return max_len

print(max_consecutive_ones([1,1,1,0,0,0,1,1,1,1,0], 2))  # 6

Time Complexity

• Naive approach: O(n²) or O(n·k)
• Sliding window: O(n)

The key insight: each element enters and exits the window exactly once!

Common Mistakes

1. Off-by-one errors: Carefully track left, right indices
2. Not updating window state: Remember to add AND remove elements
3. Wrong condition: Make sure shrink condition is correct
4. Forgetting edge cases: Empty array, k > n, etc.

When NOT to Use

Sliding window doesn't work when:

• Elements don't need to be contiguous
• You need all possible subarrays
• The problem requires dynamic programming