Introduction to Sliding Window Pattern

Some problems do not give a fixed size. The window grows while it is valid. When it becomes invalid, move the left boundary until it is valid again.

Each value enters the window at most once. Each value also leaves at most once. Both boundaries move only from left to right.

Therefore, the total time complexity is usually O(N).

A variable-size solution may contain a loop inside another loop. It is still O(N) because the left boundary never returns to an earlier index.

Recognize it when

Sliding Window may be useful when:

• The problem asks about a contiguous subarray or contiguous substring.
• The question asks for the longest or shortest valid range.
• The question asks for the maximum or minimum value across ranges.
• The problem gives a fixed size such as K.
• Your first solution starts at each index and scans forward again.
• A small summary can describe the current range.

Words such as "consecutive," "neighbouring," and "substring" are strong signals. They tell you that values cannot be skipped.

Do not use this pattern when:

• Values may be skipped. That creates a subsequence and often needs Dynamic Programming.
• You need a pair or triplet in a sorted array. Use Two Pointers.
• You need answers for many independent range-sum queries. Use Prefix Sum.
• You need the maximum or minimum value inside every window. A Monotonic Queue may be better.

The template

This template handles a window whose size changes:

function slidingWindow(input):
    windowStart = 0
    summary = empty
    best = starting value

    for windowEnd from 0 to length(input) - 1:
        add input[windowEnd] to summary

        while window is not valid:
            remove input[windowStart] from summary
            windowStart = windowStart + 1

        best = update answer using current window

    return best

Three parts change from problem to problem:

1. The summary that describes the window.
2. The condition that says whether the window is valid.
3. The answer that you record.

Use while when shrinking a variable-size window. One removal may not make the window valid again.

For a fixed-size window, shrink when its length becomes greater than K.

The current window length is:

windowEnd - windowStart + 1

Variants in this chapter

Start with the fixed-size version. Then learn how to grow and shrink a variable-size window.

Watch out for

• Using if instead of while. A variable-size window may need several removals.
• Forgetting the outgoing value. Remove it from the sum, count, product, or frequency map.
• Using the wrong window length. Include + 1 because both boundary positions belong to the window.
• Deleting a frequency too early. Reduce its count first, and delete the key only when the count becomes zero.
• Scanning the full frequency map on every step. Keep a separate count of satisfied requirements when possible.
• Calling the algorithm O(N²) because it has two loops. Each boundary moves at most N times.

How this compares with nearby patterns

Sliding Window and Two Pointers both use two indices. Their indices represent different things.

In Sliding Window, the indices are the boundaries of one contiguous range. In Two Pointers, the indices usually identify two values being compared.

Key takeaways

• A sliding window always represents a contiguous range.
• Update a small summary when values enter or leave the window.
• Each boundary moves only forward, so the total work is usually O(N).
• Use while when one removal may not make a variable-size window valid.
• The summary, validity condition, and recorded answer change between problems.
• If values may be skipped, Sliding Window is usually not the correct pattern.

Now apply this pattern to Maximum Sum Subarray of Size K.