Sliding Window: Complete Guide with Examples

Coding Patterns - Guide to 30 Core Algorithm Patterns

The Sliding Window pattern answers questions about contiguous subarrays and substrings. Questions of the form “longest”, “shortest”, or “does any window contain” usually have a brute-force answer that checks every possible segment, which costs

O(N^2)

. Sliding window keeps one segment alive at a time and only updates it as it moves. That turns a nested loop into a single pass and buys

O(N)

time for a whole family of problems.

The key difference between sliding window and a generic two-pointer scan is that the two pointers never restart. Both move forward through the input, which means every element is examined at most twice. Once when the window’s right edge reaches it, and once when the window’s left edge passes it.

Definition: keep a window bounded by left and right indices. Add elements at the right edge to grow the window, remove elements at the left edge to shrink it, and maintain a running state (usually a sum or a frequency table) that makes the window easy to evaluate at any moment.

Real-World Analogy

Imagine a stylus and a piece of ticker tape. The tape has a number printed on each segment, and you need to answer questions about a contiguous stretch of tape, like how many segments cover a given total. Reading the tape again for each new question is wasteful. Instead you keep the last segment that entered the window and the first segment that left it. To know the sum of a new window, you do not recount the whole thing. You add the number on the segment entering from the right, and subtract the number of the segment leaving on the left.

That is the entire sliding window tradeoff. One entry, one exit, done. The bookkeeping replaces the repeated work proportional to the window size.

Visual Explanation

The variable-size form is the most useful to sketch, because the fixed-size form is just the variable form where the left edge moves together with the right on every step.

    graph TD
    A["left = 0, right = 0, window state = empty"] --> B["Move right, an element enters the window"]
    B --> C{"Does the window satisfy the requirement?"}
    C -- "No, keep expanding" --> B
    C -- "Yes" --> D["Record the window as a candidate result"]
    D --> E["Shrink: the left element leaves, left++"]
    E --> F{"Does the window still satisfy it?"}
    F -- "Yes" --> D
    F -- "No" --> B
    B --> Z["right reaches the end, scan complete"]

The diagram shows the single rule that does the work. The right edge only ever expands, and the left edge only ever shrinks. When a window does not satisfy the requirement, the only way to fix it is to add elements on the right. When it does satisfy the requirement, the only way to find a better answer is to drop elements from the left. No pointer ever moves backward.

Fixed-size windows are the same picture with a simpler narrowing. The window is valid only when it has exactly k elements, so the result is recorded at every step once the window is full, and the left edge moves, always keeping exactly k elements inside.

What the window state really is

For a requirement like “sum at least 7”, the state is a single running sum. For “no two repeated characters”, the state is a frequency table of the characters currently inside the window. The data structure matches whatever condition the problem checks. The mechanics of the window never change, only the meaning of the state.

When to Use Sliding Window

The pattern fits problems with these characteristics:

The answer is contiguous by requirement. The window only makes sense for subarrays and substrings. If a problem allows skipping elements, sliding window is not the tool.
The state updates in constant time on entry and exit. A running sum qualifies. A character count table qualifies. State that needs re-scanning the whole window each time defeats the purpose.
The constraint is monotonic. Expanding the window can only push the constraint in one direction and shrinking it in the other. “Sum is at least 7” has this monotone growth. “Contains at most k distinct characters” behaves like a count that increases on entry and decreases on exit, so it stays usable.
The problem phrases the answer as “longest”, “shortest”, or “at most k”. Those phrasings usually mean a validity condition that the shrink step can enforce. A target sum, a count limit, or a fixed length attached to “contiguous” is the same signal in a different form.

There is a trap here. Sliding window works on sums only when all elements are non-negative. With negative numbers, expanding a window can lower the sum, so the monotonic assumption breaks. Kadane’s algorithm from the Array Manipulation page is the right tool for maximum subarray sums with negatives.

Complexity Analysis

The linear time comes from the moving pointers. Each element enters the window once when the right pointer passes it, and leaves at most once when the left pointer passes it.

Window Type	Time	Space	Notes
Fixed-size	O(N)	O(1)	Each element enters and leaves exactly once
Variable-size	O(N)	O(1)	Each element enters and leaves at most once
Frequency tracking	O(N)	O(K)	O(K) is the number of distinct characters in the input

The time derivation is where most learners get confused. The inner while loop looks like a nested loop, which would be

O(N^2)

. But the inner loop never restarts the left pointer. Across the whole run, left and right each visit every index exactly once, so the total number of operations is a small multiple of N, not N squared.

The space is

O(1)

when the state is a single number like a sum. With a frequency table, the state grows with the number of distinct characters that can be in the window, so the space becomes

O(K)

, where K is the alphabet size (typically 26 for lowercase letters).

Memorizing complexity tradeoffs is half the battle. The other half is remembering them under pressure. Review this pattern with spaced repetition so the analysis becomes automatic by interview day.

Common Mistakes

Off-by-one in the window length. A window from left to right inclusive has right - left + 1 elements. The missing + 1 is the most common bug in this code. It produces answers that are correct for every window of length 2 and up and silently wrong for length 1, which surfaces as a single hidden test failure.

To catch it, trace the smallest window you can, with both pointers at index 0. Record right - left + 1 and force yourself to compute the hand result before trusting the formula.

Recording the result after the window is invalidated. For a minimum-length question the result must be recorded at the moment the window becomes valid, and again after each shrink while it stays valid. Beginners often shrink first and then record, which skips the smallest valid window by one. For a maximum-length question, the mistake is the mirror image. Recording a length inside the invalidating while loop overstates the answer by the size of one invalid window.

The mental model to fix this is that validity and size are not the same. Ask what shape the state is in the moment you take the measurement.

Starting to record before a fixed window is full. A fixed-size window of size k needs the first k elements before any answer means anything. Recording a window of size k/2 or smaller produces nonsense. Check the current index against k - 1 before recording, in a zero-based loop.

Forgetting a window can never exist. When no subarray satisfies the constraint, the sentinel value (0 for length, or the max value that means “not found”) escapes the loop unchanged. The return path must check for that sentinel explicitly. Forgetting the sentinel check turns an impossible problem into a silent wrong answer.

Resetting the left pointer. Re-running the left edge back to the start to “try again” breaks the invariant that makes the algorithm linear. The left pointer moves only forward. When the window is invalid, shrink from the left. There is nothing left at earlier positions, and with a monotonic constraint they can never be part of a valid window again.

These mistakes are expensive because they look correct until they fail on a hidden test case. Our review decks flag exactly these edge cases and drill them until they are reflex. Add this pattern to your queue .

Related Patterns

Two Pointers: Two pointers that both move forward with a window between them is what this page covers. The two-pointers page covers pointers that start at opposite ends and close in on each other. Same family of ideas, different track.
Array Manipulation: Kadane’s algorithm from the array manipulation page is the close cousin that works with negative numbers. Where sliding window shrinks monotonically, Kadane restarts a running sum entirely. When sums can be negative, reach for Kadane.
Prefix Sum: The prefix sum pattern answers the same window-sum questions with
O(N)
preprocessing and
O(1)
queries per window. Sliding window is a single pass with
O(1)
space, so use it when one window property is enough and the input is non-negative.
Monotonic Deque: For “maximum value inside a window” questions, the deque keeps the window maximum ready at each position. See the queue page for the sliding window maximum technique.

Next Steps

Once the concept is clear, the next step is making the code automatic. The code templates page has the fixed-size and variable-size versions in six languages, and the practice problems page walks through them from Easy to Hard with full solutions.

Reading about a pattern once is not enough to own it in an interview. Practice this pattern with spaced repetition and turn recognition into recall.