Template / Mental Model

Sliding Window – Template and Mental Model

The sliding-window technique is used to process continuous portions of an array or string efficiently.

A window represents a contiguous range between two boundaries:

Window = [left, right]

Instead of recalculating every possible subarray or substring from the beginning, the window is updated by:

• Adding the new element entering from the right.

• Removing the old element leaving from the left.

• Updating only the information affected by these changes.

Consider:

arr = [2, 1, 5, 1, 3]

For a window of size 3, the possible windows are:

[2, 1, 5]

[1, 5, 1]

[5, 1, 3]

When moving from the first window to the second:

• Remove 2 from the left.

• Add 1 from the right.

The complete window does not need to be processed again.

The Sliding-Window Mental Model

A useful mental model is:

The right pointer explores new elements, the left pointer removes unnecessary elements, the maintained state describes the current window, and the answer records the best valid window seen so far.

Every sliding-window solution can be understood through five actions:

1. Expand: Move right forward to include a new element.

2. Update: Add the new element’s contribution to the maintained state.

3. Validate: Check whether the current window satisfies the required condition.

4. Shrink: Move left forward and remove elements until the required condition is restored.

5. Record: Use the current valid window to update the answer.

The exact order of shrinking and recording depends on whether the problem asks for a fixed-size window, longest valid window, smallest valid window, or number of valid windows.

What Does the Window Represent?

For an array or string, the current window contains every element from index left to index right, both inclusive.

The window length is:

right - left + 1

For:

left = 2

right = 5

The window length is:

5 - 2 + 1 = 4

The +1 is required because both boundary positions belong to the window.

Depending on the problem, the maintained window state may contain:

The maintained state must always describe exactly the elements currently present inside the window.

The Window Invariant

A window invariant is a condition that remains true whenever the window is used to update the answer.

Examples include:

• The window contains at most K distinct values.

• The window contains no repeated characters.

• The window sum is smaller than or equal to a limit.

• The window contains all required characters.

• The window size is exactly K.

Before writing the solution, clearly define:

• What makes the window valid?

• What information is required to check validity?

• Which element enters when right moves?

• Which element leaves when left moves?

• When should the answer be updated?

Most sliding-window errors occur when the maintained state and the actual window no longer match.

Types of Sliding Windows

Sliding-window problems are mainly divided into two categories:

1. Fixed-size sliding window

2. Variable-size sliding window

1. Fixed-Size Sliding Window

A fixed-size window always contains exactly K elements.

The right pointer expands the window. Whenever its size becomes greater than K, the leftmost element is removed and left moves forward.

This pattern is commonly used for:

• Maximum sum of a subarray of size K

• Maximum average subarray of size K

• Number of distinct elements in every window of size K

• First negative number in every window of size K

• Maximum or minimum element in every window of size K

Example: Maximum Sum of a Subarray of Size K

Consider:

arr = [2, 1, 5, 1, 3]

K = 3

Window 1

[2, 1, 5]

Sum = 2 + 1 + 5 = 8

Current maximum:

8

Window 2

Remove 2 and add the next 1:

[1, 5, 1]

Sum = 8 - 2 + 1 = 7

Current maximum remains:

8

Window 3

Remove the first 1 and add 3:

[5, 1, 3]

Sum = 7 - 1 + 3 = 9

Updated maximum:

9

Therefore, the maximum sum is:

9

Template

• Initialize left at the beginning and prepare the required window state.

• Move right forward and add the current element to the state.

• If the window size exceeds K, remove the element at left and move left forward.

• When the window size becomes exactly K, use its state to update the answer.

• Continue until right reaches the end of the input.

Time Complexity: O(N) because each element enters and leaves the window at most once.

Space Complexity: Depends on the maintained state. A running sum requires O(1) space, while a frequency map may require additional space.

2. Variable-Size Sliding Window

A variable-size window changes its length according to a condition.

The right pointer expands the window by including new elements. If the condition becomes invalid, the left pointer shrinks the window until validity is restored.

This pattern is commonly used for:

• Longest substring without repeating characters

• Longest subarray with at most K distinct values

• Longest substring after at most K replacements

• Smallest subarray with sum at least a target

• Minimum window substring

• Number of subarrays satisfying a condition

Example: Longest Substring Without Repeating Characters

Consider:

s = "abca"

The window must contain no repeated character.

At right = 0

Include a:

Window = "a"

The window is valid.

Maximum length:

1

At right = 1

Include b:

Window = "ab"

The window is valid.

Maximum length:

2

At right = 2

Include c:

Window = "abc"

The window is valid.

Maximum length:

3

At right = 3

Include a:

Window = "abca"

The character a appears twice, so the window is invalid.

Remove characters from the left until the previous a is removed:

Window = "bca"

The window is valid again.

Maximum length remains:

3

Therefore, the longest substring without repeating characters has length 3.

Template

• Place left at the beginning and initialize the state of an empty window.

• Move right forward and add the current element to the state.

• Check whether the expanded window violates the required condition.

• While the window is invalid, remove the element at left and move left forward.

• After restoring validity, use the current window to update the answer.

• Repeat until every right position has been processed.

Time Complexity: O(N) because both pointers move only forward.

Space Complexity: Depends on the information maintained for the current window.

Template for the Longest Valid Window

When the problem asks for the longest window satisfying a condition, the window should first be restored to a valid state.

The mental process is:

• Expand the window using right.

• Add the incoming element to the state.

• Shrink from the left while the condition is invalid.

• After validity is restored, calculate the current length.

• Update the maximum length.

The answer is updated after shrinking because an invalid window cannot be considered.

Examples include:

• Longest substring without repeating characters

• Longest subarray with at most K distinct values

• Maximum consecutive ones after at most K flips

Template for the Smallest Valid Window

When the problem asks for the smallest window satisfying a condition, expansion and shrinking are handled differently.

The mental process is:

• Expand the window until it becomes valid.

• Once valid, record its current length.

• Remove the leftmost element to check whether a smaller valid window exists.

• Continue recording and shrinking while the window remains valid.

• Resume expansion when the condition becomes invalid.

Here, the answer is updated inside the shrinking process because every valid window is a candidate, and shrinking may produce a smaller one.

Examples include:

• Minimum-size subarray with sum at least a target

• Minimum window substring

• Smallest substring containing all required characters

Template for Counting Valid Windows

Some problems ask for the number of subarrays or substrings satisfying a condition.

After the window is made valid for a particular right, every starting position from left to right may form a valid window ending at right.

The number of such windows is:

right - left + 1

For example, if:

left = 2

right = 5

then the valid windows ending at 5 begin at indices:

2, 3, 4, 5

Their count is:

5 - 2 + 1 = 4

This counting rule is commonly used for conditions such as:

• At most K distinct values

• At most K odd numbers

• Product smaller than a target

• Sum within a limit when the required monotonic property exists

The condition must ensure that every smaller suffix of the current valid window is also valid.

Where Should the Answer Be Updated?

The position of the answer update depends on the problem.

Updating the answer at the wrong position may include invalid windows or miss valid candidates.

Expand, Shrink, and Record

A reliable way to reason about any sliding-window problem is to answer three questions.

1. What Happens When the Window Expands?

Identify how the incoming element changes the state.

Examples:

• Add its value to the running sum.

• Increase its frequency.

• Increase the distinct count if its previous frequency was zero.

• Increase the zero count if the element is zero.

• Increase the matched count when a required frequency is reached.

2. When Must the Window Shrink?

Define the exact invalid condition.

Examples:

• The window contains more than K distinct values.

• A character appears more than once.

• The sum becomes greater than the allowed limit.

• The number of zeros exceeds K.

• The window size becomes greater than the fixed size.

3. What Happens When the Window Shrinks?

Reverse the contribution of the outgoing element before moving left.

Examples:

• Subtract its value from the running sum.

• Decrease its frequency.

• Decrease the distinct count when its frequency becomes zero.

• Decrease the zero count when a zero leaves.

• Update the matched count when a required frequency is no longer satisfied.

The add and remove operations should be logical opposites so that the maintained state remains accurate.

When Should while Be Used?

Use a while-based shrinking process when the window must be completely restored to a valid state before it can be evaluated.

A single left movement may not be enough.

Consider a window that allows at most two distinct characters. If one character occurs several times near the left boundary, removing only one occurrence may leave three distinct characters inside the window.

Repeated shrinking is required until the invalid character is completely removed or the condition becomes valid again.

A while-based template is the safe general choice for:

• Restoring a valid window

• Finding the smallest valid window

• Counting valid windows

• Problems where each valid state must be processed

When Can a Single if Be Used?

Some longest-window problems allow an optimized non-shrinking template.

When the expanded window becomes invalid:

• Remove only one element from the left.

• Move left forward once.

• Allow the maintained window length to remain equal to the largest length reached so far.

Because both left and right move once during that iteration, the window does not become larger while it remains invalid. Therefore, it cannot create a new maximum answer.

This optimization can be used only when:

• The problem asks for the maximum window length.

• The window length is intentionally kept non-decreasing.

• An invalid maintained window cannot increase the recorded answer.

• The correctness of removing only one element can be proved.

A while loop should not be replaced with an if mechanically. Minimum-window and counting problems generally require full shrinking.

Why Is Sliding Window Usually O(N)?

A variable-size template may contain a shrinking loop inside the main traversal, but this does not automatically make it O(N²).

The right pointer moves from the beginning to the end at most once.

The left pointer also moves from the beginning to the end at most once.

Therefore:

• Each element enters the window at most once.

• Each element leaves the window at most once.

• The total pointer movement is at most proportional to 2N.

After ignoring constant factors, the total traversal takes:

O(N)

This analysis assumes that adding, removing, and checking the maintained state take constant time or constant average time.

How to Recognize a Sliding-Window Problem

Consider sliding window when:

• The problem asks about a contiguous subarray or substring.

• A range must be expanded and shrunk repeatedly.

• The answer involves a maximum, minimum, or count of valid ranges.

• The current range can be updated using the entering and leaving elements.

• Both boundaries can move only forward.

• Removing elements from the left can restore an invalid condition.

• Recalculating every range would otherwise require nested loops.

A useful recognition question is:

Can the result for the next contiguous range be obtained by removing the outgoing element and adding the incoming element?

If yes, sliding window may be appropriate.

When Sliding Window Does Not Work

Sliding window should not be applied only because a problem involves subarrays or substrings.

It may not work when:

• The required elements are not contiguous.

• Removing elements from the left does not predictably restore validity.

• Pointer movement may need to go backward.

• The complete state cannot be updated from only the entering and leaving elements.

• The condition is not monotonic under expansion and shrinking.

• The problem requires considering arbitrary combinations rather than continuous ranges.

For example, a variable-size window based on a sum limit often depends on the elements being non-negative. With negative values, expanding the window may decrease the sum and shrinking it may increase the sum. The usual pointer movement is no longer reliable.

Possible alternatives include:

• Prefix sum with hashing

• Binary search

• Dynamic programming

• Monotonic deque

• Fenwick tree or segment tree

• Direct enumeration when constraints are small

Fixed-size windows can still process negative values because their movement does not depend on a sum-validity rule.

General Sliding-Window Checklist

Before implementing a sliding-window solution, determine:

• Is the required range contiguous?

• Is the window size fixed or variable?

• What do left and right represent?

• What information must be maintained?

• How is an incoming element added?

• What exactly makes the window invalid?

• How is an outgoing element removed?

• Must shrinking continue until validity is restored?

• Should the answer be updated before or after shrinking?

• What is the correct window-length formula?

• Does the condition remain reliable for negative values?

• What happens when the input is empty or no valid window exists?

Advantages of Sliding Window

• It can reduce nested-loop solutions from O(N²) to O(N).

• It avoids recalculating information for overlapping ranges.

• It often uses only constant or limited additional space.

• It works well for arrays, strings, and streaming data.

• It supports fixed-size, longest, smallest, and counting problems.

• It combines naturally with frequency maps, sets, and deques.

Limitations of Sliding Window

• It is mainly applicable to contiguous ranges.

• Variable-size windows usually require a monotonic condition.

• Incorrect state removal can make the window inconsistent.

• Some conditions require additional data structures.

• Negative values may invalidate sum-based movement rules.

• The answer-update position changes between problem types.

• An optimized single-if template is not valid for every problem.

Common Mistakes

• Forgetting that the window length is right - left + 1.

• Updating the answer while the window is still invalid.

• Moving left without removing its element from the maintained state.

• Removing an element after moving left, causing the wrong value to be removed.

• Using a single if when repeated shrinking is required.

• Using a while loop incorrectly for a fixed-size window.

• Decreasing a frequency but not removing its zero-frequency entry when map size represents distinct values.

• Assuming the shrinking loop makes the complexity O(N²).

• Applying a sum-based variable window to arrays containing negative values without proving correctness.

• Forgetting to process the first complete fixed-size window.

• Using one template unchanged for longest, smallest, and counting problems.

FAQs

Q1. Why does a shrinking while loop not make the sliding-window solution O(N²)?

Although the shrinking loop may run multiple times during one iteration, the left pointer moves forward at most N times across the complete execution. Combined with at most N right-pointer movements, the total traversal remains O(N).

Q2. When can a single if replace the shrinking while loop?

A single if can be used in certain longest-window optimizations where the maintained window is never allowed to grow beyond the best valid length while invalid. This requires a correctness proof and should not be used for minimum-window or counting problems that need complete validity restoration.

Q3. Why do negative numbers break many variable-size sum windows?

With non-negative elements, expanding a window cannot decrease its sum, and shrinking cannot increase it. Negative values remove this monotonic behaviour, so pointer movement can skip valid answers. Prefix sums with hashing or other techniques may be required.

Q4. How can the number of windows with exactly K occurrences or distinct values be calculated?

Many exact-count problems can be transformed using:

Exactly(K) = AtMost(K) - AtMost(K - 1)

Each “at most” value can often be calculated using a sliding window.

Q5. When is a monotonic deque required with a sliding window?

A deque is useful when every window requires its maximum or minimum element. A running sum can be updated directly, but removing the current maximum or minimum may require finding the next best value. A monotonic deque maintains these candidates efficiently.