Sliding Window Pattern

If you are preparing for coding interviews, you will eventually run into problems involving subarrays, substrings, consecutive elements, longest/shortest ranges, or windows of size K.

Many of these problems look different on the surface, but underneath, they are often variations of the same idea:

Keep a window over the input, move it efficiently, and maintain only the information you need about that window.

This technique is called Sliding Window.

For many problems, it can turn a solution from O(N²) into O(N).

But there is one important warning:

Not every subarray or substring problem is a Sliding Window problem.

The real skill is not memorizing nine solutions. It is learning to recognize which window pattern applies, when to expand, when to shrink, and what state to maintain.

This guide builds that mental model step by step.

1. What Is a Sliding Window?

Consider this array:

[2, 1, 5, 1, 3, 2]

Suppose the problem asks:

Find the maximum sum of 3 consecutive elements

The possible windows are:

[2, 1, 5] → 8
   [1, 5, 1] → 7
      [5, 1, 3] → 9
         [1, 3, 2] → 6

The answer is:

9

A brute-force solution calculates every window from scratch.

But look at two neighboring windows:

[2, 1, 5]
   [1, 5, 1]

Most of their elements are the same.

Instead of calculating the second sum again:

2 + 1 + 5 = 8
1 + 5 + 1 = 7

we can simply:

Old sum = 8

Remove 2
Add 1

New sum = 8 - 2 + 1
        = 7

That is the core idea:

┌───────────────┐
│ Current Window         |
└───────────────┘
          ↓           ↓
       Remove        Add
       leaving       entering
       element       element

Instead of rebuilding every subarray, we reuse the work from the previous window.

2. How Do You Recognize a Sliding Window Problem?

When you see an array or string problem, ask four questions.

Question 1: Is the input linear?

Usually:

Array
String

Sliding Window is naturally suited to data where elements have a left-to-right order.

Question 2: Are we dealing with contiguous elements?

Look for words such as:

Subarray
Substring
Consecutive
Contiguous
Window

For example:

[1, 2, 3, 4, 5]

This is a contiguous range:

[2, 3, 4]

But this is not:

[1, 3, 5]

because the selected elements are not adjacent.

Question 3: Is the problem asking something about that range?

Common clues include:

Maximum
Minimum
Longest
Shortest
Count
At most K
Exactly K
Size K

When contiguous + one of these conditions appears together, Sliding Window should be one of the first patterns you consider.

But there is still one more question.

Question 4: Can the window be maintained efficiently?

This is the most important question.

You need to be able to answer:

What makes my current window valid, and can I efficiently restore validity by moving left?

If moving left and right does not give you a reliable way to solve the problem, Sliding Window may not be appropriate.

3. The Sliding Window Map

Most problems can first be classified into:

SLIDING WINDOW
                           │
              ┌────────────┴────────────┐
              ↓                         ↓
         FIXED SIZE                VARIABLE SIZE
              │                         │
           Size = K               ┌─────┴─────┐
                                  ↓           ↓
                               Longest     Shortest
                                  │           │
                                  ↓           ↓
                            Shrink when   Shrink while
                              invalid       valid

There are also two important special patterns:

Maximum / Minimum
in every K window
        ↓
Monotonic Deque

and:

Exactly K
     ↓
AtMost(K) - AtMost(K - 1)

Let’s understand each pattern.

4. Pattern #1 — Fixed-Size Window

This is the simplest Sliding Window pattern.

Use it when the problem explicitly gives you a window size:

K

Typical questions look like:

Find the maximum sum of a subarray of size K.

or:

Find the first negative number in every window of size K.

The window always contains exactly K elements.

Example: Maximum Sum of Size K

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

The windows are:

[2, 1, 5]
   [1, 5, 1]
      [5, 1, 3]
         [1, 3, 2]

The process is:

Expand right
     ↓
Window reaches K
     ↓
Calculate answer
     ↓
Remove left element
     ↓
Move right

Code

def max_sum(arr, k):
    left = 0
    window_sum = 0
    answer = float("-inf")
 
    for right in range(len(arr)):
        window_sum += arr[right]
 
        if right - left + 1 == k:
            answer = max(answer, window_sum)
 
            window_sum -= arr[left]
            left += 1
 
    return answer

The important part is:

right - left + 1 == k

This tells us that the current window has exactly K elements.

Complexity

Time:  O(N)
Space: O(1)

5. Fixed Window Does Not Mean Fixed State

The window size may be fixed, but what you maintain inside the window depends on the problem.

For example:

ProblemWindow StateMaximum sumRunning sumFirst negativeQueue / DequeCount anagramsFrequency mapMaximum in every windowMonotonic deque

This leads to an important rule:

The window determines how elements move. The problem determines what state you maintain.

6. Pattern #2 — Variable-Size Window

Now the size of the window is not fixed.

Instead, the window grows and shrinks depending on a condition.

The general structure is:

left = 0
 
for right in range(len(arr)):
 
    add(arr[right])
 
    while window_is_invalid():
        remove(arr[left])
        left += 1
    update_answer()

Think of it as:

Expand with right
       ↓
Check condition
       ↓
Invalid?
       ↓
Shrink with left
       ↓
Valid again
       ↓
Update answer

There are two major versions:

Longest
Shortest

And the key difference is when you shrink.

7. Variable Window — Longest

Use this pattern when the problem asks:

Find the longest/largest valid subarray or substring.

The rule is:

Shrink when the window becomes invalid.

Expand
  ↓
Window invalid?
  ↓
YES
  ↓
Shrink
  ↓
Valid again
  ↓
Update maximum length

Template

def longest_window(arr):
    left = 0
    answer = 0
 
    for right in range(len(arr)):
 
        add(arr[right])
 
        while invalid():
            remove(arr[left])
            left += 1
        answer = max(answer, right - left + 1)
 
    return answer

The key idea:

Valid   → keep expanding
Invalid → shrink

Why?

Because we want the largest possible valid window.

8. Example — Longest Substring With K Unique Characters

Problem:

Find the longest substring containing exactly K unique characters.

Example:

s = "aabacbebebe"
k = 3

We maintain a frequency map:

{
    'a': 2,
    'b': 1,
    'c': 1
}

The number of unique characters is:

len(freq)

Our invalid condition is:

unique > K

So:

while len(freq) > k:
    remove(s[left])
    left += 1

Once the window is valid, if:

unique == K

we update the answer.

The important thing is that “exactly K” here is a condition on the current window, so we first restore validity using:

unique <= K

and then record the answer only when:

unique == K

9. Example — Longest Substring Without Repeating Characters

Problem:

Find the longest substring where every character appears only once.

Example:

"abcabcbb"

Start expanding:

a
ab
abc

The window is valid.

Now we add another a:

abca

The window is invalid because a appears twice.

So we shrink from the left:

abca
↑

Remove the first a:

bca

Now the window is valid again.

The pattern is:

Add right
    ↓
Duplicate?
    ↓
YES
    ↓
Shrink left
    ↓
Valid again
    ↓
Update maximum

This is the same Longest Variable Window pattern.

Only the state is different.

You might use:

Set

or a:

Frequency Map

depending on the implementation.

10. Example — Pick Toys

Suppose you have a row of toys:

A B A C B B A

You can pick toys from a contiguous range, but you can have at most 2 different types.

This is equivalent to:

Find the longest substring containing at most 2 distinct characters.

The condition is:

unique types <= 2

If we encounter:

unique types > 2

the window becomes invalid.

So we shrink from the left.

Again:

Longest
+
At Most K
=
Variable Sliding Window

This is an excellent example of why recognizing the underlying condition matters more than memorizing the problem name.

11. Variable Window — Shortest

Now suppose the problem asks:

Find the smallest/shortest window satisfying a condition.

The strategy changes.

Instead of shrinking when invalid, we:

Shrink while the window remains valid.

The process becomes:

Expand
  ↓
Window valid?
  ↓
YES
  ↓
Record answer
  ↓
Shrink left
  ↓
Still valid?
  ↓
YES → shrink again
NO  → stop

Template

def shortest_window(arr):
    left = 0
    answer = float("inf")
    for right in range(len(arr)):
 
        add(arr[right])
 
        while valid():
 
            answer = min(answer, right - left + 1)
 
            remove(arr[left])
            left += 1
 
    return answer

Think:

Invalid → expand
Valid   → shrink

Why?

Because once the window becomes valid, our goal is to make it as small as possible.

12. Example — Minimum Window Substring

Problem:

Find the smallest substring of S containing all characters of T**.

Example:

S = "ADOBECODEBANC"
T = "ABC"

We expand right until the window contains:

A
B
C

For example:

ADOBEC

The window is now valid.

But we don’t stop.

We try to make it smaller:

ADOBEC
↑
remove from left

If the window still contains everything required, keep shrinking.

Eventually, removing another character makes the window invalid.

At that point:

stop shrinking
expand right again

The pattern is:

Find valid window
       ↓
Shrink while valid
       ↓
Record minimum
       ↓
Continue expanding

The answer for this example is:

BANC

13. The Most Important Rule: Longest vs Shortest

If you remember only one distinction from this article, remember this:

┌───────────────────────────────┐
│ LONGEST                       │
│                               │
│ Shrink when INVALID           │
└───────────────────────────────┘
 

┌───────────────────────────────┐
│ SHORTEST                      │
│                               │
│ Shrink while VALID            │
└───────────────────────────────┘

Longest

We want the window to be as large as possible:

Valid   → keep expanding
Invalid → shrink

Shortest

We want the window to be as small as possible:

Invalid → keep expanding
Valid   → shrink

This simple distinction solves a surprising number of Sliding Window problems.

14. Pattern #3 — At Most K

Another extremely common form is:

Count subarrays containing at most K elements satisfying some condition.

For example:

Count subarrays containing at most K odd numbers.

We maintain:

number_of_odds

As right moves:

Add arr[right]

If:

number_of_odds > K

the window is invalid.

So we shrink:

while number_of_odds > k:
    remove(arr[left])
    left += 1

Now the window is valid again.

But here comes an important counting trick.

Suppose the current valid window is:

[ left ........ right ]

Every subarray ending at right and starting anywhere from left through right is also valid.

For example:

[left ................ right]
       [............... right]
              [........ right]
                    [.... right]
                         [.. right]
                            [right]

How many are there?

right - left + 1

Therefore:

answer += right - left + 1

This gives us the number of valid subarrays ending at right.

15. Pattern #4 — Exactly K

Now suppose the problem asks:

Count subarrays with exactly K distinct elements.

A powerful technique is:

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

Why does this work?

Suppose:

K = 2

AtMost(2) contains windows with:

0 distinct
1 distinct
2 distinct

AtMost(1) contains:

0 distinct
1 distinct

Subtracting them leaves:

Exactly 2

So:

AtMost(2)
-
AtMost(1)
=
Exactly(2)

In general:

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

This is one of the most useful transformations in Sliding Window.

16. A Generic At-Most-K Template

def at_most_k(arr, k):
    left = 0
    answer = 0
    state = 0
 
    for right in range(len(arr)):
        update_state(arr[right])
        while state > k:
            remove_state(arr[left])
            left += 1
        answer += right - left + 1
    return answer

Then:

exactly_k = at_most_k(arr, k) - at_most_k(arr, k - 1)

The key idea is:

AtMost(K)
    ↓
Keep window valid
    ↓
Count all valid subarrays ending at right

17. Pattern #5 — Monotonic Deque

Consider this problem:

Find the maximum value in every window of size K.

Example:

arr = [1, 3, -1, -3, 5, 3, 6, 7]
K = 3

Output:

[3, 3, 5, 5, 6, 7]

A normal fixed-size window tells us which elements belong to the window, but we still need to efficiently find the maximum.

Scanning every window would cost:

O(NK)

We can do better with a monotonic deque.

The Idea

For a maximum, maintain candidate values in decreasing order:

[9, 7, 5, 2]

If a new value 10 arrives:

[9, 7, 5, 2]

none of those smaller values can ever become the maximum while 10 is still inside the window.

So they can be removed.

The deque becomes:

[10]

Rules

For every new element:

1. Remove expired indices from the front.

2. Remove smaller elements from the back.

3. Add the new index.

4. The front of the deque is the maximum.

Notice that we store indices, not just values.

Why?

Because we need to know whether an element has left the current window.

18. Maximum vs Minimum

This is easy to mix up.

For maximum:

Decreasing Deque

Example:

[9, 7, 5, 2]

For minimum:

Increasing Deque

Example:

[2, 5, 7, 9]

So remember:

Maximum → decreasing deque
Minimum → increasing deque

The monotonic deque lets us solve sliding-window maximum/minimum problems in:

O(N)

because every index enters and leaves the deque at most once.

19. What State Should You Maintain?

A Sliding Window is not just about two pointers.

You also need state that describes the current window.

Ask:

What information do I need to know whether this window is valid or to calculate its answer?

Common choices are:

Running Sum

Useful for:

Maximum sum
Minimum sum
Sum-based conditions

Maintain it with:

window_sum += arr[right]
window_sum -= arr[left]

Frequency Map

Useful for:

Character frequencies
Distinct elements
Anagrams
Minimum Window Substring

Example:

freq[arr[right]] += 1

When removing:

freq[arr[left]] -= 1

If a count reaches zero, remove the key.

Set

Useful when you only care whether an element already exists.

For example:

Longest substring without repeating characters

Queue / Deque

Useful for:

First negative number
Window maximum/minimum

Monotonic Deque

Specifically useful for:

Maximum in every K window
Minimum in every K window

20. When Sliding Window Fails

This is just as important as knowing when it works.

Seeing the word:

subarray

does not automatically mean Sliding Window.

The key requirement is that moving the boundaries must allow us to make reliable progress.

21. Negative Numbers and Sum Problems

Consider:

[2, -5, 10, -2, 3]

If we add an element, the sum can:

Increase
or
Decrease

If we remove an element, the sum can also:

Increase
or
Decrease

Therefore, we cannot blindly use rules such as:

sum > K → move left
sum < K → move right

when arbitrary negative numbers are allowed.

For example:

Find the longest subarray with sum K.

If negative numbers are allowed, the standard Sliding Window approach may fail.

A common alternative is:

Prefix Sum + HashMap

The important lesson is:

Do not apply Sliding Window just because the problem says “subarray.”

22. Why Positive Numbers Make Sliding Window Easier

Consider:

[2, 3, 1, 5, 2]

All values are positive.

Then:

Add an element
      ↓
Sum increases

Remove an element
      ↓
Sum decreases

This predictable behavior makes certain decisions safe.

For example, for a problem such as:

Find the smallest subarray with sum ≥ K.

we can often use:

sum < K
    ↓
expand

sum >= K
    ↓
shrink

because adding positive values can only increase the sum and removing positive values can only decrease it.

This monotonic behavior is what makes the window technique work.

23. Sliding Window vs Two Pointers

Sliding Window and Two Pointers are closely related, but they are not identical.

Sliding Window

Usually:

left  →
right →

Both pointers move in the same direction.

We care about the range:

[left ........ right]
       WINDOW

Typical problems involve:

Subarrays
Substrings
Contiguous ranges

Two Pointers

Two pointers often look like:

left →       ← right

A classic example is a sorted array:

[1, 2, 3, 4, 6]
 ↑           ↑
left        right

Suppose we need two numbers whose sum is 7.

1 + 6 = 7

For a sorted-array problem such as Two Sum II, two pointers are appropriate.

For ordinary unsorted Two Sum, a HashMap is generally the standard approach.

The broader lesson is:

Sliding Window is about maintaining a contiguous range. Two Pointers is a broader family of techniques involving multiple moving indices.

24. Sliding Window vs Prefix Sum

A useful rule of thumb:

Consider Sliding Window when:

You can safely determine:

Move right
Move left

based on the current window.

Consider Prefix Sum when:

You need relationships between sums at different positions, especially when negative numbers destroy the monotonic behavior required by Sliding Window.

A common pattern is:

Prefix Sum + HashMap

For example:

Longest subarray with sum K

with arbitrary positive and negative numbers is commonly solved this way.

25. The Four Core Templates

Instead of memorizing dozens of solutions, memorize these structures.

Fixed Window

left = 0
 
for right in range(len(arr)):
 
    add(arr[right])
    if right - left + 1 == k:
        update_answer()
        remove(arr[left])
        left += 1

Think:

Window size = K

Longest Variable Window

left = 0
 
for right in range(len(arr)):
    add(arr[right])
    while invalid():
        remove(arr[left])
        left += 1
    update_max_answer()

Think:

Longest
→ Shrink when invalid

Shortest Variable Window

left = 0
 
for right in range(len(arr)):
    add(arr[right])
    while valid():
        update_min_answer()
        remove(arr[left])
        left += 1

Think:

Shortest
→ Shrink while valid

At Most K

left = 0
answer = 0
 
for right in range(len(arr)):
 
    add(arr[right])
 
    while state > k:
        remove(arr[left])
        left += 1
 
    answer += right - left + 1

Think:

AtMost(K)
→ Keep the window valid
→ Count valid subarrays ending at right

26. The Sliding Window Decision Tree

When you encounter a new problem, walk through this checklist:

ARRAY / STRING
                        │
                        ↓
                 Is it CONTIGUOUS?
                   │           │
                  NO          YES
                   │           │
            Other pattern      ↓
                        Is size K given?
                          │          │
                         YES        NO
                          │          │
                          ↓          ↓
                    Fixed Window   Variable
                                   Window
                                      │
                              ┌───────┴───────┐
                              ↓               ↓
                           Longest         Shortest
                              │               │
                              ↓               ↓
                       Shrink when      Shrink while
                         INVALID          VALID

Then check for special cases:

Maximum / Minimum
in every K window?
        ↓
Monotonic Deque

Exactly K?
        ↓
AtMost(K) - AtMost(K - 1)

Sum + negative numbers?
        ↓
Be careful
        ↓
Prefix Sum + HashMap may be better

27. Sliding Window Cheat Sheet

Problem CluePattern”Size K”Fixed Window”K consecutive”Fixed Window”Longest…”Longest Variable Window”Shortest…”Shortest Variable Window”At most K”At-Most Window”Exactly K”AtMost(K) − AtMost(K−1)”Maximum in every K window”Monotonic Deque”Minimum in every K window”Monotonic Deque”Anagram occurrences”Fixed Window + Frequency Map”No repeating characters”Longest Variable Window”K unique characters”Variable Window + Frequency Map”Minimum Window Substring”Shortest Variable Window”Sum = K” + negative numbersPrefix Sum + HashMapSorted array + pairTwo Pointers

28. A Nine-Problem Learning Path

If you are learning Sliding Window from scratch, these problems form a useful progression:

1. Maximum Sum of Size K
          ↓
    Learn Fixed Window
          ↓
2. First Negative in Every K Window
          ↓
    Learn Queue + Window
          ↓
3. Count Anagrams
          ↓
    Learn Frequency Map
          ↓
4. Sliding Window Maximum
          ↓
    Learn Monotonic Deque
          ↓
5. Longest Subarray Sum K
          ↓
    Learn Variable Window
          ↓
6. Longest Substring with K Unique Characters
          ↓
    Learn Frequency + Condition
          ↓
7. Longest Substring Without Repeating Characters
          ↓
    Learn Valid / Invalid Window
          ↓
8. Pick Toys
          ↓
    Learn At-Most K
          ↓
9. Minimum Window Substring
          ↓
    Learn Shortest Valid Window

These problems are useful because each introduces a slightly different piece of the overall pattern.

You are not really learning nine unrelated algorithms.

You are learning variations of the same framework.

29. What You Actually Need to Memorize

You do not need to memorize every Sliding Window solution.

Instead, remember these rules:

1. Contiguous array/string
        ↓
   Think Sliding Window

2. Size K
        ↓
   Fixed Window

3. Longest
        ↓
   Shrink when INVALID

4. Shortest
        ↓
   Shrink while VALID

5. At Most K
        ↓
   Keep the window valid

6. Exactly K
        ↓
   AtMost(K) - AtMost(K - 1)

7. Max/Min in every K window
        ↓
   Monotonic Deque

8. Sum + negative numbers
        ↓
   Don't blindly use Sliding Window

30. The Final Mental Model

The entire pattern can be reduced to this:

SLIDING WINDOW
                              │
                 ┌────────────┴────────────┐
                 ↓                         ↓
             FIXED SIZE               VARIABLE SIZE
                 │                         │
               Size K                ┌─────┴─────┐
                                     ↓           ↓
                                  LONGEST      SHORTEST
                                     │           │
                                     ↓           ↓
                              INVALID →       VALID →
                                shrink         shrink

And remember the three important special cases:

MAX / MIN in every window
        ↓
MONOTONIC DEQUE

EXACTLY K
        ↓
AT MOST K - AT MOST K-1

SUM + NEGATIVE NUMBERS
        ↓
Check whether Sliding Window is valid
        ↓
PREFIX SUM + HASHMAP may be better

Final Takeaway

The goal of learning Sliding Window is not to memorize nine solutions.

The goal is to look at a new problem and immediately ask:

What is my window?

What makes the window valid?

When should I move left?

What state do I need to maintain?

If you can answer those four questions, you can usually build the solution yourself.

That is the real power of the Sliding Window pattern:

Don’t memorize the problems. Learn how the window moves.