Sliding Window Pattern | CodeTutor

Sliding Window

Easy

15 questions using this pattern

What is Sliding Window?

Maintain a window of elements that slides through the data, tracking a constraint or computing aggregates. This transforms O(n*k) brute force into O(n) by incrementally updating the window instead of recalculating from scratch.

Think of it like this...

Imagine looking at a landscape through a train window. As the train moves forward, the scenery at the back of your view disappears while new scenery appears at the front. You don't need to memorize the entire journey—just keep track of what's currently visible through your window.

Another analogy: a cashier's sliding tray at a bank. As new items are added to one end, old items fall off the other. You only count what's on the tray at any moment.

Core Concept

The sliding window technique avoids redundant computation by maintaining state as the window moves. Instead of recalculating the entire window each time, you add what enters and remove what leaves.

There are two main types:

Fixed-size window: Window size is constant (e.g., "find max sum of k elements")
Variable-size window: Window expands and contracts based on constraints (e.g., "longest substring with at most 2 distinct characters")

The key insight is that consecutive windows share most of their elements. Only the edges change, so only update those.

Maximum Sum Subarray of Size K

Sliding Window

def max_sum_subarray(nums: list[int], k: int) -> int:

    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

Variables

k=3

Problem

We have an array [2, 1, 5, 1, 3, 2] and need to find the maximum sum of any 3 consecutive elements.

1/22

Visual Walkthrough

Example: Maximum sum of 3 consecutive elements

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

Window 1: [2, 1, 5] = 8    (calculate full sum)
           └─────┘

Window 2: [1, 5, 1] = 8-2+1 = 7  (remove 2, add 1)
              └─────┘

Window 3: [5, 1, 3] = 7-1+3 = 9  (remove 1, add 3) ← Maximum!
                 └─────┘

Window 4: [1, 3, 2] = 9-5+2 = 6  (remove 5, add 2)
                    └─────┘

Variable window: Longest substring with at most 2 distinct chars

String: "eceba"

"e"     → 1 distinct, expand  → length 1
"ec"    → 2 distinct, expand  → length 2
"ece"   → 2 distinct, expand  → length 3 ← Answer!
"eceb"  → 3 distinct, shrink from left
"ceb"   → 3 distinct, shrink from left
"eb"    → 2 distinct, expand  → length 2
"eba"   → 3 distinct, shrink...

Code Template

Use this skeleton as a starting point for problems using this pattern:

python

def fixed_window(arr: list, k: int) -> int:
    """Fixed-size sliding window."""
    n = len(arr)
    if n < k:
        return 0

    # Calculate initial window
    window_sum = sum(arr[:k])
    max_sum = window_sum

    # Slide the window
    for i in range(k, n):
        window_sum += arr[i] - arr[i - k]  # Add new, remove old
        max_sum = max(max_sum, window_sum)

    return max_sum


def variable_window(s: str, k: int) -> int:
    """Variable-size sliding window."""
    char_count = {}
    left = 0
    max_length = 0

    for right in range(len(s)):
        # Expand: add character at right
        char_count[s[right]] = char_count.get(s[right], 0) + 1

        # Contract: shrink from left if constraint violated
        while len(char_count) > k:
            char_count[s[left]] -= 1
            if char_count[s[left]] == 0:
                del char_count[s[left]]
            left += 1

        # Update answer
        max_length = max(max_length, right - left + 1)

    return max_length

Recognition Signals

Look for these keywords and patterns in problem descriptions:

contiguous subarraysubstringmaximum sum of k elementswindowconsecutiveat most k distinctminimum windowlongest substringsliding

When to Use

Finding subarrays/substrings with specific properties
Maximum/minimum sum of fixed-size windows
Longest substring with at most K distinct characters
Problems mentioning "contiguous" elements

Common Mistakes

Forgetting to handle window smaller than required

When array length is less than window size k, trying to create a window causes index errors or incorrect results.

Fix:

Add an early check:

if len(arr) < k:
    return 0  # or appropriate default

Off-by-one in variable window

When calculating window length, using right - left instead of right - left + 1 gives length off by one.

Fix:

Window length is always right - left + 1 (inclusive on both ends).

Not cleaning up empty entries in hash map

Pattern Variations

Fixed-size window

Window size stays constant throughout. Simple slide operation: add one element, remove one element.

Examples: Maximum Sum Subarray of Size K, Find All Anagrams

Variable-size (shrinkable)

Window expands freely but contracts when constraints are violated. Uses a while loop to shrink until valid.

Examples: Longest Substring Without Repeating, Minimum Window Substring

Two-pointer variant

Some problems use two pointers that feel like sliding window but track different metrics. The mechanics are similar.

Examples: Container With Most Water, Trapping Rain Water

Caterpillar method

Another name for the variable sliding window, emphasizing how the window stretches and contracts like a caterpillar moving.

Examples: Common in competitive programming contexts

Learning Path

1Warmup0/2

Start here to build foundational understanding.

Calculate Digit Sum of a StringOptimal

#2243Easy

Contains Duplicate IIOptimal

#219Easy

2Core Practice0/10

Master the pattern with these representative problems.

Alert Using Same Key-Card Three or More Times in a One Hour PeriodOptimal

#1604Medium

Binary String With Substrings Representing 1 To NOptimal

#1016Medium

Binary Subarrays With SumOptimal

#930Medium

Check If a String Contains All Binary Codes of Size KOptimal

#1461Medium

Jump Game VIIOptimal

#1871Medium

Longest Substring Without Repeating CharactersOptimal

#3Medium

Longest Turbulent SubarrayOptimal

#978Medium

Minimum Size Subarray Sum

#209Medium

Permutation in StringOptimal

#567Medium

Subarray Product Less Than KOptimal

#713Medium

3Challenge0/3

Test your mastery with complex variations.

Maximum Fruits Harvested After at Most K StepsOptimal

#2106Hard

Minimum Window SubstringOptimal

#76Hard

Sliding Window Maximum

#239Hard

Prerequisites

Learn these patterns first:

Two Pointers

Use two pointers to traverse data from different positions, often moving toward or away from each other. This technique transforms O(n²) brute force into O(n) by eliminating redundant comparisons.

Related Patterns

Explore similar techniques:

Two Pointers

Use two pointers to traverse data from different positions, often moving toward or away from each other. This technique transforms O(n²) brute force into O(n) by eliminating redundant comparisons.

Prefix Sum

Precompute cumulative sums to answer range sum queries in O(1) time. This transforms repeated O(n) range calculations into O(n) preprocessing plus O(1) per query, making it essential for problems involving subarray sums.

When shrinking a variable window, decrementing a counter to 0 but not removing the key causes the distinct count to be wrong.

Fix:

Always delete keys when count reaches 0:

if char_count[s[left]] == 0:
    del char_count[s[left]]