Coding Patterns

What are the main sliding window patterns?

Sliding window problems use two pointers to maintain a moving range over an array or string. Common variations include fixed-size windows, variable-size windows, frequency-map windows, and monotonic-deque windows.

Coding PatternsSliding WindowTwo PointersArraysStrings

The Short Answer

Sliding window is a pattern for problems involving contiguous subarrays or substrings.

Instead of recomputing every possible range from scratch, you keep a moving window and update useful state as the right and left pointers move.

The key idea: expand the window, update state, shrink the window when needed, and update the answer along the way.

The Real Problem It Solves

Many brute-force solutions check every subarray or substring.

java

for (int left = 0; left < n; left++) {
    for (int right = left; right < n; right++) {
        // recompute something about nums[left..right]
    }
}

That is often O(n²), or even worse if computing the window state is expensive.

Sliding window asks:

Can I reuse the work from the previous window instead of starting over each time?

Mental Model

Expand right

Add new item

Check condition

Shrink left

Update answer

java

left = 0

for right in range(n):
    add nums[right] to window

    while window is invalid:
        remove nums[left]
        left++

    update answer

That template is the heart of many variable-size sliding window problems.

Pattern 1: Fixed-Size Window

Use this when the problem gives you a fixed length k.

The window size never changes. You add the new right element and remove the old left element.

java

int windowSum = 0;

for (int right = 0; right < nums.length; right++) {
    windowSum += nums[right];

    if (right >= k) {
        windowSum -= nums[right - k];
    }

    if (right >= k - 1) {
        answer = Math.max(answer, windowSum);
    }
}

When to Use

The problem says “size k”, “length k”, “exactly k elements”, or “every window of k”.

Example Problem

Maximum Sum Subarray of Size K

Pattern 2: Variable-Size Window

Use this when the window grows and shrinks based on a condition.

Usually, you expand with the right pointer until the window becomes invalid, then shrink from the left until it becomes valid again.

java

int left = 0;

for (int right = 0; right < nums.length; right++) {
    add(nums[right]);

    while (windowIsInvalid()) {
        remove(nums[left]);
        left++;
    }

    updateAnswer();
}

When to Use

The problem asks for longest/shortest subarray or substring that satisfies a condition.

Example Problem

Longest Substring Without Repeating Characters

Pattern 3: Frequency Map Window

Use this when the window needs to track character or element counts.

This is common for strings, anagrams, permutations, and “contains all required characters” problems.

java

Map<Character, Integer> window = new HashMap<>();

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

    while (windowNeedsShrinking()) {
        char leftChar = s.charAt(left);
        window.merge(leftChar, -1, Integer::sum);

        if (window.get(leftChar) == 0) {
            window.remove(leftChar);
        }

        left++;
    }
}

When to Use

You need counts of characters/items inside the current window.

Example Problem

Find All Anagrams in a String

Pattern 4: Minimum Window With Requirements

This is a special frequency-map version where the window must contain required characters or counts.

The main challenge is tracking when the window satisfies all requirements.

java

Map<Character, Integer> need = new HashMap<>();
Map<Character, Integer> window = new HashMap<>();

int have = 0;
int required = need.size();

for (int right = 0; right < s.length(); right++) {
    addRightChar();

    while (have == required) {
        updateMinimumAnswer();
        removeLeftChar();
        left++;
    }
}

When to Use

The problem asks for the shortest substring containing all required characters or words.

Example Problem

Minimum Window Substring

Pattern 5: At Most K Window

This is one of the most important variable-window patterns.

The condition usually looks like:

java

numberOfDistinctItems <= k

When the window has too many distinct items, shrink from the left until it becomes valid again.

java

while (distinctCount > k) {
    remove(nums[left]);
    left++;
}

answer = Math.max(answer, right - left + 1);

When to Use

Problems involving “at most k distinct”, “at most k zeros”, or “replace at most k characters”.

Example Problem

Longest Substring with At Most K Distinct Characters

Pattern 6: Exactly K Using At Most K

Some “exactly K” problems are easier if you convert them into two “at most” calculations.

exactlyK = atMostK(k) - atMostK(k - 1)

This is common when counting subarrays rather than finding just the longest one.

java

countExactlyK(k) =
    countAtMostK(k) - countAtMostK(k - 1);

When to Use

Counting subarrays with exactly K distinct values, odds, or other features.

Example Problem

Subarrays with K Different Integers

Pattern 7: Monotonic Deque Window

Use this when the window needs the current maximum or minimum efficiently.

A monotonic deque keeps useful candidates in order, so the front of the deque can give the max or min for the current window. This is the standard optimization for Sliding Window Maximum.

java

Deque<Integer> deque = new ArrayDeque<>();

for (int right = 0; right < nums.length; right++) {
    while (!deque.isEmpty()
            && nums[deque.peekLast()] <= nums[right]) {
        deque.pollLast();
    }

    deque.offerLast(right);

    if (deque.peekFirst() <= right - k) {
        deque.pollFirst();
    }

    if (right >= k - 1) {
        answer.add(nums[deque.peekFirst()]);
    }
}

When to Use

Fixed-size windows where you need max/min repeatedly.

Example Problem

Sliding Window Maximum

How to Recognize Sliding Window

The problem mentions contiguous subarray or substring.
You are asked for longest, shortest, maximum, minimum, or count.
You can update the answer when an element enters or leaves.
Brute force checks many overlapping ranges.
The input is usually an array or string.

Problems to Cover Later

Fixed-Size Window

Maximum Sum Subarray of Size K

Variable-Size Window

Longest Substring Without Repeating Characters

Frequency Map Window

Find All Anagrams in a String

Minimum Window Requirements

Minimum Window Substring

At Most K Window

Longest Substring with At Most K Distinct Characters

Exactly K via At Most K

Subarrays with K Different Integers

Monotonic Deque Window

Sliding Window Maximum

The Interview-Friendly Explanation

Sliding window is used for contiguous subarray or substring problems. The main idea is to maintain a window with left and right pointers and update state incrementally as the window moves. Fixed-size windows keep length k. Variable-size windows expand and shrink based on validity. Frequency-map windows track counts. Monotonic-deque windows maintain max or min efficiently.

Common Interview Follow-Ups

How do you know if sliding window applies?

Look for contiguous subarray or substring problems where brute force checks many overlapping ranges.

What is the difference between fixed and variable window?

Fixed window has a constant size k. Variable window changes size based on a condition, usually expanding with right and shrinking with left.

Why use a frequency map?

Use a frequency map when the window needs to know counts of characters or values, such as anagrams, permutations, or distinct elements.

Why use a monotonic deque?

Use a monotonic deque when you need the maximum or minimum of each window efficiently, without scanning the whole window each time.

Is sliding window always O(n)?

Usually yes when each pointer only moves forward. Some variants may include map or deque operations, but the core pointer movement is linear.

Final Takeaway

Sliding window is about reusing work. Instead of recomputing every contiguous range from scratch, maintain a moving window and update only what changed when the window expands or shrinks.