Sliding Window

Sliding window is a specialized two-pointer family where the pointers define a contiguous interval and you maintain information about that entire interval as it moves.

What Makes Sliding Window Different?

Many problems have two moving boundaries. That alone does not make them sliding window problems.

A problem belongs to this family when:

• the answer depends on the subarray or substring between left and right
• you can update the window state incrementally as elements enter or leave
• you maintain a condition that tells you whether the window is valid

What is an Invariant?

An invariant is a statement that stays true before and after every iteration.

For sliding window, the invariant often looks like one of these:

• “the current window is valid”
• “the current window contains no duplicates”
• “the current window sum is at most the target”
• “the frequency map matches the characters currently inside the window”

The invariant gives the loop its structure:

• expand the window by moving right
• update the window state
• if the invariant breaks, shrink from the left until it holds again
• update the answer only when you know the invariant is satisfied

Why Invariants Matter

Without an invariant, shrinking the window becomes arbitrary. You no longer know:

• when the window is valid
• when to update the answer
• why the left pointer should stop moving
• The invariant is the reason the algorithm is correct.

The Main Subtypes

1. Fixed-size windows

2. Flexible-size windows with a validity rule

3. Frequency-tracking windows

How Sliding Window Differs From Other Two-Pointer Families

Compare it with Container With Most Water:

• In sliding window, the interval itself has meaning.
• In container, the interval is just the remaining search space.

Compare it with Remove Duplicates:

• In sliding window, both pointers describe a live window.
• In compaction, the left part of the array is already the answer prefix.

A Practical Template

A common variable-size sliding window has this shape:

1. Add the new rightmost element.
2. Update the window state.
3. While the invariant is broken, remove elements from the left.
4. Once the invariant is restored, update the answer.

The exact data structure changes from problem to problem, but the logic stays the same.

As you work through this section, keep asking: