Sliding Window Technique: Patterns, Template & Practice

The sliding window algorithm is what you reach for when a problem says contiguous and then asks for a longest, a shortest, a maximum, or a count. Rather than recomputing an aggregate for every window from scratch, you move a range across the data and update state at its two edges — one element in, one element out. That is the whole idea, and it collapses O(n·k) into O(n).

Everything genuinely hard about this pattern lives in three decisions: what state the window carries, what makes the window invalid, and where in the loop you are allowed to record the answer. Get those three right and the variants below are small edits to the same twenty lines. This post gives you copy-pasteable templates in Python and Java, the four variants that actually get asked, and the argument for why the nested while is still linear.

(It is the same-direction case of the two pointers family, but the useful mental model is a range with state, not a pair of indices.)

Recognition: the phrase in the problem tells you the variant

Read the problem statement for these phrases and the variant falls out before you write a line.

The last two rows are the ones that separate people who know the pattern from people who have memorised it, and they are the reason for the section after the templates.

Template 1: the fixed-size sliding window

The window length k never changes. Seed the first window, then for every step add the entering element and subtract the leaving one.

def max_sum_subarray(nums, k):
    if k <= 0 or k > len(nums):
        return None
    window_sum = sum(nums[:k])          # seed the first window
    best = window_sum
    for right in range(k, len(nums)):
        window_sum += nums[right] - nums[right - k]   # in at right, out at right - k
        best = max(best, window_sum)
    return best

static long maxSumSubarray(int[] nums, int k) {
    if (k <= 0 || k > nums.length) throw new IllegalArgumentException("bad window size");
    long windowSum = 0;
    for (int i = 0; i < k; i++) windowSum += nums[i];   // seed the first window
    long best = windowSum;
    for (int right = k; right < nums.length; right++) {
        windowSum += nums[right] - nums[right - k];     // in at right, out at right - k
        best = Math.max(best, windowSum);
    }
    return best;
}

Use long for the running sum in Java unless the constraints rule out overflow — a window of 10⁵ values near Integer.MAX_VALUE overflows silently, and interviewers do notice.

Template 2: the variable-size sliding window

This is the workhorse. Most of the sliding window leetcode problems you will meet are this shape with a different definition of "invalid".

def longest_substring_without_repeats(s):
    count = {}
    left = best = 0
    for right, ch in enumerate(s):
        count[ch] = count.get(ch, 0) + 1        # 1. admit the entering element
        while count[ch] > 1:                    # 2. restore the invariant
            out = s[left]
            count[out] -= 1
            if count[out] == 0:
                del count[out]                  #    keep the map's size meaningful
            left += 1
        best = max(best, right - left + 1)      # 3. the window here is always valid
    return best

static int longestSubstringWithoutRepeats(String s) {
    Map<Character, Integer> count = new HashMap<>();
    int left = 0, best = 0;
    for (int right = 0; right < s.length(); right++) {
        char in = s.charAt(right);
        count.merge(in, 1, Integer::sum);                 // 1. admit
        while (count.get(in) > 1) {                       // 2. restore the invariant
            char out = s.charAt(left++);
            if (count.merge(out, -1, Integer::sum) == 0) count.remove(out);
        }
        best = Math.max(best, right - left + 1);          // 3. record
    }
    return best;
}

Three slots, and every variant is a substitution into them:

1. Admit. Update state with the element entering at right. Always exactly one element.
2. Restore. while (invalid), evict left and undo its contribution. A while, not an if — one entering element can force several evictions.
3. Record. By the time control reaches here the window is valid by construction, so this is where longest-window answers are taken.

That last slot is the highest-value sentence in this post. For longest problems you record after the shrink loop; for shortest problems you record inside it, because a valid window can usually still be tightened and the answer is the last valid state before the invariant breaks. Same template, one line moved, completely different family of problems.

The precondition nobody states

The shrink loop is only correct if validity is downward-closed: if a window is valid, every window contained inside it is also valid. That is what lets you conclude "the window got invalid, so evicting from the left is the only thing that can help" — and it is silently true for the constraints these problems use.

• "At most K distinct" — remove a character and the distinct count can only fall. Downward-closed.
• "Sum ≥ target over non-negative numbers" — remove an element and the sum can only fall. Downward-closed.
• "Sum ≥ target when negatives are allowed" — not downward-closed. Removing a −5 makes the sum go up, so a window being invalid tells you nothing about whether to shrink. This is why Subarray Sum Equals K is a prefix-sum-plus-hash-map problem and not a window problem, and saying so out loud in an interview is worth more than solving the easy version quickly.

When you cannot decide, test it on two elements: take a valid window, delete something from one end, and ask whether it must still be valid. If the answer is "not necessarily", the sliding window pattern does not apply directly — though it may still apply to a reformulated version, which is precisely the exactly-K trick below.

The four variants that get asked

1. Longest substring with at most K distinct characters

Template 2, with the invalid condition on the map's size rather than on any single count.

def longest_at_most_k_distinct(s, k):
    count = {}
    left = best = 0
    for right, ch in enumerate(s):
        count[ch] = count.get(ch, 0) + 1
        while len(count) > k:                 # too many distinct characters
            out = s[left]
            count[out] -= 1
            if count[out] == 0:
                del count[out]                # only now does distinct-count drop
            left += 1
        best = max(best, right - left + 1)
    return best

Traced on s = "eceba", k = 2:

At right = 3 the window admitted b, hit three distinct characters, and evicted twice — e first (its count fell 2 → 1, still present, still invalid) and then c (count fell to 0, key deleted, valid again). Two evictions from one admission is exactly why step 2 is a while.

The deletion of zero-count keys is load-bearing. Leave the key in the map at count 0 and len(count) counts characters that are no longer in the window, the loop shrinks forever, and left runs off the end.

2. Shortest window containing all of T (Minimum Window Substring)

The shape flips: expand until the window is valid, then shrink while it stays valid, recording each time. Duplicates in t are what makes this harder than it looks — t = "AABC" needs two As, so a set will not do.

from collections import Counter

def min_window(s, t):
    if not t or len(s) < len(t):
        return ""
    need = Counter(t)
    missing = len(t)                    # characters still owed, duplicates included
    best_len, best_start = float("inf"), 0
    left = 0
    for right, ch in enumerate(s):
        if need[ch] > 0:                # this copy is one we actually needed
            missing -= 1
        need[ch] -= 1                   # may go negative: a surplus inside the window
        while missing == 0:             # valid — shrink while it stays valid
            if right - left + 1 < best_len:
                best_len, best_start = right - left + 1, left
            out = s[left]
            need[out] += 1
            if need[out] > 0:           # we gave back a character we needed
                missing += 1
            left += 1
    return "" if best_len == float("inf") else s[best_start : best_start + best_len]

The negative counts are the feature, not a bug. need[ch] below zero means the window holds more copies of ch than t requires — surplus you can evict for free. missing only moves when a count crosses zero, so the validity check stays O(1) instead of comparing two maps every step. Clamping need at zero "to make it tidy" is the classic wrong fix: the surplus information disappears and missing starts incrementing on evictions that did no harm, so the window stops shrinking through junk characters.

On s = "ADOBECODEBANC", t = "ABC", the window first becomes valid at ADOBEC (length 6, recorded), shrinks to DOBEC and breaks; later ODEBANC (7) is beaten by EBANC (5), then BANC (4) — recorded as it tightens, which is why the answer must be taken inside the loop.

3. Exactly K, via at-most-K minus at-most-(K−1)

This is the single most useful idea in the pattern and almost nobody teaches it. You cannot shrink on "exactly K distinct", because exactly-K is not downward-closed — a sub-window of an exactly-3-distinct window might have 2. So you never write it. You write the easy version twice.

def subarrays_with_exactly_k_distinct(nums, k):
    return at_most_k_distinct(nums, k) - at_most_k_distinct(nums, k - 1)

def at_most_k_distinct(nums, k):
    if k < 0:
        return 0                                # guards the k = 0 call above
    count = {}
    left = total = 0
    for right, x in enumerate(nums):
        count[x] = count.get(x, 0) + 1
        while len(count) > k:
            out = nums[left]
            count[out] -= 1
            if count[out] == 0:
                del count[out]
            left += 1
        total += right - left + 1               # every window ending at right is valid
    return total

Two things are doing the work. The first is total += right - left + 1: once the window [left, right] is the longest valid one ending at right, every suffix of it is also valid — downward-closure again — so there are exactly right - left + 1 valid subarrays ending at that index. The second is the subtraction: every subarray with at most K distinct values has either exactly K, or at most K−1, and nothing else, so the difference is precisely the exactly-K count.

On nums = [1, 2, 1, 2, 3], k = 2: at-most-2 gives 12, at-most-1 gives 5, so exactly-2 is 7. The same trick converts "exactly K odd numbers" (count odds instead of distinct values), "exactly K zeros", and any other exactly-K count into two runs of a template you already have. That is a Hard problem reduced to a Medium you can write from memory.

4. Maximum of every fixed window, in O(n)

Fixed-size window, but the aggregate is a maximum — and max is not invertible. A sum lets you subtract the departing element; a max, once it departs, leaves you with no idea what the new max is. A heap gets you O(n log n). A monotonic deque of indices gets you O(n).

from collections import deque

def max_sliding_window(nums, k):
    dq = deque()                       # indices; their values decrease front → back
    out = []
    for right, x in enumerate(nums):
        while dq and nums[dq[-1]] <= x:
            dq.pop()                   # x is newer AND larger: the tail can never win
        dq.append(right)
        if dq[0] <= right - k:
            dq.popleft()               # the front has slid out of the window
        if right >= k - 1:
            out.append(nums[dq[0]])    # front is the max of the current window
    return out

static int[] maxSlidingWindow(int[] nums, int k) {
    Deque<Integer> dq = new ArrayDeque<>();          // indices, values decreasing
    int[] out = new int[nums.length - k + 1];
    for (int right = 0; right < nums.length; right++) {
        while (!dq.isEmpty() && nums[dq.peekLast()] <= nums[right]) dq.pollLast();
        dq.addLast(right);
        if (dq.peekFirst() <= right - k) dq.pollFirst();
        if (right >= k - 1) out[right - k + 1] = nums[dq.peekFirst()];
    }
    return out;
}

The invariant to say out loud: the deque holds only indices that could still become the maximum of some future window. An element that is both older and smaller than the one entering is dominated forever, so it is discarded on entry rather than tracked. Store indices, not values — the eviction at the front is a position test, and you cannot do it with values. On [1,3,-1,-3,5,3,6,7] with k = 3 this yields [3,3,5,5,6,7].

Why it is O(n), despite the nested while

The code has a loop inside a loop, so the reflex answer is O(n²). The reflex is wrong, and being able to say why is a genuine senior signal.

Count the inner loop globally rather than per iteration. left starts at 0, only ever increases, and can never exceed n. Every execution of the shrink body advances left by exactly one. Therefore the shrink body runs at most n times across the entire scan — not per outer step, in total. Add the n admissions and you get at most 2n state updates: O(n) amortised, where each element enters the window exactly once and leaves at most once.

Two caveats worth stating unprompted:

• Constant-time state updates are an assumption. Hash-map operations are O(1) expected; but if your validity check compares two frequency maps in full, you have quietly reintroduced an alphabet-sized factor and the bound becomes O(n·Σ). Track a scalar (missing, matched, len(count)) instead.
• Space is O(min(n, Σ)) for the count map — or genuinely O(1) with a fixed int[26] or int[128] array when the alphabet is bounded, which is worth mentioning for string problems. The deque variant is O(k).

Six problems, and what each one tests

• Longest Substring Without Repeating Characters (LC 3) — whether you can maintain the invariant incrementally instead of rescanning the window. The tell is whether left jumps correctly on a repeat.
• Minimum Size Subarray Sum (LC 209) — the non-negativity precondition. The follow-up is always "what if the array contains negatives?", and the expected answer is that the shrink argument collapses, not a patched loop.
• Longest Substring with At Most K Distinct Characters (LC 340) — whether you shrink on the map's size rather than on some individual count, and whether you delete zero-count keys.
• Minimum Window Substring (LC 76) — recording inside the shrink loop, plus an O(1) validity check that survives duplicates in t. This is the one that most often exposes a memorised solution.
• Subarrays with K Different Integers (LC 992) — the exactly-K subtraction. Rated Hard entirely because of the reformulation; the code is the at-most template.
• Sliding Window Maximum (LC 239) — whether you recognise a non-invertible aggregate and reach for a deque instead of a heap.

Permutation in String (LC 567) and Find All Anagrams (LC 438) are worth adding as a pair: both are fixed-size windows where the naive check compares two frequency maps every step, and the point is to maintain a single matched counter instead.

Failure modes

• Confusing fixed with variable. If the length is given, it is fixed; if the length is whatever the constraint permits, it is variable.
• Shrinking on the wrong condition. For longest problems you shrink while the window is invalid. Shrinking as soon as it becomes valid gives you the shortest window instead — the code runs, returns a plausible number, and answers a different question.
• Recording the answer in the wrong place. Inside the shrink loop for shortest, after it for longest. This single line is the most common source of a solution that is right on the sample input and wrong on the third test case.
• Counts that go negative when they should not — and clamping the ones that should. In Minimum Window Substring negatives are correct and encode surplus. In at-most-K-distinct a count reaching zero must delete the key, or the map's size lies about the window. Two opposite bugs from the same confusion: the map's size and the map's values mean different things.
• Forgetting to update state on both edges. Add the entering element and undo the leaving one. Half-updates produce off-by-a-little answers that look like an off-by-one and are not.
• A shrink branch that does not advance left. Instant infinite loop, and the easiest bug to avoid: make left += 1 unconditional in the loop body.
• Recomputing the aggregate each step. It works, it passes small tests, and it throws away the entire point — you are back at O(n·k) with more code than the brute force.
• Off-by-one in the window length. It is right - left + 1, inclusive on both ends. Write it once at the top of the file and stop rederiving it.

Practise it as a template, not as problems

Write the variable-size template from memory until the three slots are automatic, then attack the six problems above by asking only the three questions: what state, what makes it invalid, where does the answer get recorded. Nearly all of the thinking happens before you type anything. Build a schedule around it with the free study-plan generator, or work through the variants live with feedback in our DSA course.

This is one of seventeen shapes worth recognising on sight — the complete DSA patterns guide has the full recognition table and shows how the rest fit together.

More interview patterns: Two Pointers · Binary Search · Dynamic Programming · Graph Algorithms

Want the next pattern breakdown when it lands? Join the list — one email per post, nothing else.

Amit Singh teaches the DSA cohort at AlgoEngineer. He is a Senior SDE at Amazon and a Claude Certified Architect.