Sliding window algorithm: the template, Python code and how to spot it in a problem

Short answer. The sliding window algorithm keeps two indexes, left and right. Both only move forward. The stretch between them is the window. The right edge grows it. The left edge shrinks it when a condition breaks. Longest or shortest contiguous stretch problems drop from O(n²) to O(n). Below: trigger words, the template, Python code and a traced run.

What is the sliding window algorithm?

A window is a contiguous slice of an array or string. Two indexes define it. Everything between left and right is inside.

A fixed window has a set length and just slides right. A variable window grows and shrinks by a rule. The variable kind shows up more often in interviews.

Both indexes only move right. Each element enters the window once and leaves once. That is why the whole pass costs O(n).

When does a problem need a sliding window?

• "Longest substring without repeating characters."
• "Smallest subarray with sum at least k."
• "Maximum sum of k consecutive elements."
• "Does string t contain a permutation of string s."

The shared signal: a contiguous stretch with a cheap property. Moving an edge updates it in O(1). If elements need not be adjacent, a window is the wrong tool.

How does the sliding window template work?

• Set left = 0. Move right from 0 to n - 1.
• Add element right to the running state.
• While the condition is broken, remove element left and move left forward.
• The window is valid now. Update the answer with its length or content.

The inner while loop does not make it quadratic. Left walks the array once over the whole run.

What does one run look like?

String "abcabcbb", longest substring without repeats. Right reaches a, b, c: window "abc", length 3. Right hits the second a: a repeat. Move left until the first a leaves. Window "bca".

Right hits the second b: left moves past the first b. Window "cab". Right hits the second c: window "abc". Then "cb", then "b". Answer 3.

How do you write a sliding window in Python?

def longest_unique(s):
    seen = set()
    left = best = 0
    for right, ch in enumerate(s):
        while ch in seen:            # condition broken
            seen.remove(s[left])
            left += 1
        seen.add(ch)
        best = max(best, right - left + 1)
    return best

def min_subarray_len(nums, target):
    left = total = 0
    best = float("inf")
    for right, x in enumerate(nums):
        total += x
        while total >= target:      # window valid, try to shrink
            best = min(best, right - left + 1)
            total -= nums[left]
            left += 1
    return 0 if best == float("inf") else best

The second function shrinks while the window is valid. That finds the shortest one. Same skeleton, flipped condition.

How is a sliding window different from two pointers?

Trait	Sliding window	Two pointers, opposite ends
Direction	Both move right	Move towards each other
Looking for	A contiguous stretch	A pair of elements
Needs sorting	No	Usually yes
State	A counter over the window	Two values
Example	Longest Substring Without Repeating	Two Sum II

Three more pairs people confuse, and how to log them, are in two pointers vs sliding window.

How does the sliding window solve Minimum Window Substring?

Given strings s and t. Find the shortest window of s holding every letter of t. Counts included.

Count the letters of t in a dictionary called need. Move right and decrement need for each letter. Keep a counter called missing. When missing hits zero the window is valid. Shrink from the left while it stays valid, and record the best.

Each letter enters and leaves once. Time O(|s| + |t|).

What mistakes break a sliding window?

• Resetting left to zero on a violation instead of stepping it. That is O(n²).
• Updating the answer before the window is valid again.
• Computing the length as right - left instead of right - left + 1.
• Using a window for a subsequence problem, where elements can be apart.

How do you explain the sliding window in an interview?

Say: the answer is a contiguous stretch. Its property updates in O(1) per edge move. Name the two indexes and the state. Give O(n) and the reason: each index only moves right.

Then show the O(n²) brute force. Say the window removes the recomputation. That is the whole argument.

Drill this pattern on the sliding window page. The fixed-size version lives on the fixed window page.

FAQ

Does a sliding window work with negative numbers?

Not for sum problems. The condition "sum at least k" stops being monotonic. Use prefix sums with a hash map instead.

How do you store the state for strings?

A dictionary from letter to count. Or an array of 26 slots for lowercase letters. The array is faster, the dictionary is more general.

How do you spot a fixed window?

The statement gives a number k and says "consecutive". Then the window is always k long. Left equals right - k + 1.