Published

Sliding Window Technique: Patterns, Templates and 8 Solved Problems

When to use a sliding window, the three templates that cover almost every problem, and eight worked LeetCode solutions with tested Python code.

On this page · 12 sections
  1. What is the sliding window technique?
  2. When to use it: the signals
  3. Fixed vs variable windows
  4. The three templates
  5. Why it’s O(n)
  6. Eight worked problems
  7. Sliding window vs two pointers
  8. Sliding window vs prefix sums
  9. Common mistakes
  10. Practice problems by difficulty
  11. FAQ
  12. Learn it step by step

The sliding window technique turns many “check every subarray” problems from O(n²) or worse into a single O(n) pass. You keep a range [left, right] over the array or string, update a small summary of what’s inside it as the edges move, and never go back. This guide covers when to use it, the three templates you need, eight worked LeetCode problems with tested Python code, and how it differs from two pointers and prefix sums.

What is the sliding window technique?

A window is a contiguous part of the input: nums[left..right] or s[left..right]. Instead of recomputing an answer for every possible window from scratch, you:

  1. Extend the window by moving right one step and adding the new element to your summary (a running sum, a character count, the last index of each character…).
  2. Shrink it by moving left forward, removing elements from the summary, whenever the window breaks the rule (or, for “shortest” problems, while it still satisfies the rule).
  3. Record the answer from the current window.

Both left and right only move forward, so each element enters the window once and leaves at most once. That’s why the whole pass is O(n), even though the code has a while loop inside a for loop.

When to use it: the signals

Reach for a sliding window when a problem has most of these:

  • The answer is about a contiguous subarray or substring (not a subsequence).
  • It asks for the longest, shortest, maximum/minimum sum, number of windows, or “does any window…” under a condition.
  • The condition can be checked from a summary you can update incrementally: a sum, counts of characters, number of distinct values, the max inside the window.
  • Validity is monotonic: if a window is invalid, every larger window containing it is also invalid (or the reverse for “shortest” problems).

If the problem says subsequence, or the numbers can be negative and you need an exact sum, the window idea usually breaks. See sliding window vs prefix sums below.

Fixed vs variable windows

Fixed-size windowVariable-size window
Window lengthAlways kGrows and shrinks
Typical question”Max sum / average of any k consecutive elements”, “all anagrams of p in s""Longest substring with…”, “shortest subarray with sum ≥ target”
Move left whenThe window exceeds kThe window becomes invalid (longest) or while it stays valid (shortest)
Extra structureRunning sum or counts; a deque for window max/minCounts, last-seen indices, number of distinct items

The three templates

Template 1: fixed size k

window = sum(nums[:k])          # summary of the first window
best = window
for i in range(k, len(nums)):
    window += nums[i] - nums[i - k]   # add the entering element, drop the leaving one
    best = max(best, window)

Template 2: variable size, longest valid window

left = 0
for right, x in enumerate(items):
    add(x)                          # 1. extend
    while window_is_invalid():      # 2. shrink until valid again
        remove(items[left])
        left += 1
    best = max(best, right - left + 1)   # 3. the window is valid here

Template 3: variable size, shortest valid window

left = 0
for right, x in enumerate(items):
    add(x)
    while window_is_valid():        # shrink while it stays valid, recording each time
        best = min(best, right - left + 1)
        remove(items[left])
        left += 1

The only difference between templates 2 and 3 is where you record the answer: after shrinking (longest) or inside the shrink loop (shortest).

The same templates in Java

import java.util.HashMap;
import java.util.Map;

public class SlidingWindow {
    // Variable-size window template: longest substring with at most k distinct characters.
    static int longestAtMostKDistinct(String s, int k) {
        Map<Character, Integer> count = new HashMap<>();
        int left = 0, best = 0;
        for (int right = 0; right < s.length(); right++) {
            count.merge(s.charAt(right), 1, Integer::sum);       // 1. add the new element
            while (count.size() > k) {                           // 2. shrink while invalid
                char out = s.charAt(left++);
                if (count.merge(out, -1, Integer::sum) == 0) count.remove(out);
            }
            best = Math.max(best, right - left + 1);             // 3. window is valid: record
        }
        return best;
    }

    // Fixed-size window template: maximum sum of any k consecutive elements.
    static long maxSumOfK(int[] nums, int k) {
        long window = 0;
        for (int i = 0; i < k; i++) window += nums[i];
        long best = window;
        for (int i = k; i < nums.length; i++) {
            window += nums[i] - nums[i - k];                     // add the entering, drop the leaving
            best = Math.max(best, window);
        }
        return best;
    }

    public static void main(String[] args) {
        System.out.println(longestAtMostKDistinct("eceba", 2));          // 3 ("ece")
        System.out.println(maxSumOfK(new int[]{2, 1, 5, 1, 3, 2}, 3));   // 9 (5+1+3)
    }
}

Output:

3
9

Why it’s O(n)

Count the moves, not the loops. right moves n times. left also only moves forward and can never pass right, so across the whole run it moves at most n times. Every add and remove is O(1) with a hash map or array of counts, so the total is O(n) time. Space is O(k) or O(alphabet size) for the summary.

Eight worked problems

All eight solutions below come from one file that also checks each function against a brute force on 300 random inputs. Running that file prints:

12.75
3 3
4
2
[0, 6]
'BANC'
[3, 3, 5, 5, 6, 7]
7
300 random cases per problem match brute force

1. Maximum Average Subarray I (LeetCode 643): fixed window

Find the maximum average of any k consecutive numbers. This is template 1 directly; divide by k at the end.

# 643. Maximum Average Subarray I (fixed window)
def find_max_average(nums, k):
    window = sum(nums[:k])
    best = window
    for i in range(k, len(nums)):
        window += nums[i] - nums[i - k]
        best = max(best, window)
    return best / k

find_max_average([1, 12, -5, -6, 50, 3], 4) returns 12.75 (the window [12, -5, -6, 50]).

2. Longest Substring Without Repeating Characters (LeetCode 3): longest

The window is valid when no character repeats. Instead of shrinking one step at a time, remember each character’s last index and jump left just past the previous copy. The >= left check ignores copies that are already outside the window.

# 3. Longest Substring Without Repeating Characters (variable, longest)
def length_of_longest_substring(s):
    last, left, best = {}, 0, 0
    for right, ch in enumerate(s):
        if last.get(ch, -1) >= left:
            left = last[ch] + 1
        last[ch] = right
        best = max(best, right - left + 1)
    return best

"abcabcbb" → 3 ("abc"), "pwwkew" → 3 ("wke").

3. Longest Repeating Character Replacement (LeetCode 424): longest

You may change up to k characters. A window can be made uniform if length - (count of its most frequent character) ≤ k. Track counts and the highest count seen.

# 424. Longest Repeating Character Replacement (variable, longest)
def character_replacement(s, k):
    count, left, top, best = defaultdict(int), 0, 0, 0
    for right, ch in enumerate(s):
        count[ch] += 1
        top = max(top, count[ch])
        while (right - left + 1) - top > k:  # more than k cells need changing
            count[s[left]] -= 1
            left += 1
        best = max(best, right - left + 1)
    return best

top is never decreased when the window shrinks. That’s safe: the answer can only improve when a window with a higher top count appears, so a stale top never produces a wrong larger answer. "AABABBA" with k = 1 gives 4.

4. Minimum Size Subarray Sum (LeetCode 209): shortest

Shortest subarray with sum ≥ target, all numbers positive. Template 3: once the sum reaches the target, record and shrink while it stays valid.

# 209. Minimum Size Subarray Sum (variable, shortest; positive numbers)
def min_subarray_len(target, nums):
    left, total, best = 0, 0, float("inf")
    for right, x in enumerate(nums):
        total += x
        while total >= target:  # valid: shrink while it stays valid
            best = min(best, right - left + 1)
            total -= nums[left]
            left += 1
    return 0 if best == float("inf") else best

min_subarray_len(7, [2, 3, 1, 2, 4, 3]) → 2 ([4, 3]). Positivity matters: it’s what makes “remove from the left → sum goes down” true.

5. Find All Anagrams in a String (LeetCode 438): fixed window of counts

Every anagram of p is a window of length len(p) with the same character counts. Slide a fixed window, keep counts, and compare.

# 438. Find All Anagrams in a String (fixed window of counts)
def find_anagrams(s, p):
    k, need, have, out = len(p), Counter(p), Counter(), []
    for i, ch in enumerate(s):
        have[ch] += 1
        if i >= k:
            old = s[i - k]
            have[old] -= 1
            if have[old] == 0:
                del have[old]
        if have == need:
            out.append(i - k + 1)
    return out

find_anagrams("cbaebabacd", "abc") → [0, 6]. Comparing two counters costs O(alphabet) per step; with a 26-letter array, or a running “matches” counter, it’s O(1). LeetCode 567 (Permutation in String) is the same code returning a boolean.

6. Minimum Window Substring (LeetCode 76): shortest

The classic hard problem. need holds how many of each character are still required; missing is the total still outstanding. When missing hits 0 the window covers t, so shrink from the left while it still does, recording the smallest.

# 76. Minimum Window Substring (variable, shortest)
def min_window(s, t):
    need, missing = Counter(t), len(t)
    left, best = 0, (0, float("inf"))
    for right, ch in enumerate(s):
        if need[ch] > 0:
            missing -= 1
        need[ch] -= 1
        while missing == 0:
            if right - left < best[1] - best[0]:
                best = (left, right)
            need[s[left]] += 1
            if need[s[left]] > 0:
                missing += 1
            left += 1
    return "" if best[1] == float("inf") else s[best[0]: best[1] + 1]

min_window("ADOBECODEBANC", "ABC") → "BANC". Characters that aren’t in t go negative in need, which is exactly what lets the shrink step skip them.

7. Sliding Window Maximum (LeetCode 239): fixed window + monotonic deque

A running variable can’t tell you the maximum after the old maximum leaves. Keep a deque of indices whose values are decreasing: pop smaller values from the back when a new value arrives (they can never be the maximum again), and pop the front when it slides out.

# 239. Sliding Window Maximum (fixed window + monotonic deque)
def max_sliding_window(nums, k):
    dq, out = deque(), []
    for i, x in enumerate(nums):
        while dq and nums[dq[-1]] <= x:
            dq.pop()
        dq.append(i)
        if dq[0] <= i - k:
            dq.popleft()
        if i >= k - 1:
            out.append(nums[dq[0]])
    return out

[1, 3, -1, -3, 5, 3, 6, 7] with k = 3 → [3, 3, 5, 5, 6, 7], in O(n). The sliding window maximum lesson has a full dry run and a Java version.

8. Subarrays with K Different Integers (LeetCode 992): counting windows

“Exactly k distinct” has no single shrink rule: a window with exactly k distinct values can be extended or shortened and still have k. So count with a trick: exactly(k) = atMost(k) − atMost(k − 1). For “at most”, every valid window ending at right contributes right - left + 1 subarrays.

# 992. Subarrays with K Different Integers (counting: exactly(K) = atMost(K) - atMost(K-1))
def subarrays_with_k_distinct(nums, k):
    def at_most(k):
        count, left, total = defaultdict(int), 0, 0
        for right, x in enumerate(nums):
            if count[x] == 0:
                k -= 1
            count[x] += 1
            while k < 0:
                count[nums[left]] -= 1
                if count[nums[left]] == 0:
                    k += 1
                left += 1
            total += right - left + 1  # every window ending at `right` and starting in [left, right]
        return total
    return at_most(k) - at_most(k - 1)

[1, 2, 1, 2, 3] with k = 2 → 7. The same trick solves “count subarrays with exactly k odd numbers” (LeetCode 1248) and “binary subarrays with sum” (LeetCode 930).

Sliding window vs two pointers

Sliding window is a special case of two pointers, and the names get mixed up. The practical difference:

Sliding windowTwo pointers (opposite ends)
Pointer movementBoth move forward, same directionStart at both ends, move towards each other
What mattersEverything between the pointersUsually just the two elements at the pointers
InputAny array or stringTypically sorted, or symmetric (palindromes)
ExamplesLongest substring without repeats, minimum windowTwo Sum II, 3Sum, container with most water

If the question is about the contents of a contiguous range, it’s a window. If it’s about a pair, and sorting helps, it’s opposite-end two pointers. The two pointers technique guide and the two pointers lesson cover the second family.

Sliding window vs prefix sums

“Subarray sum equals k” looks like a window problem but isn’t when numbers can be negative: adding a negative number can make an over-target window valid again, so you can’t decide when to shrink. Use a prefix sum plus a hash map of earlier prefix sums instead. The rule of thumb:

  • All numbers non-negative and you want ≥ / ≤ a target → sliding window.
  • Numbers can be negative, or you need an exact sum → prefix sums.

The prefix sum lesson works through this case.

Common mistakes

  • Recording the answer in the wrong place. Longest: after the shrink loop. Shortest: inside it.
  • Using if instead of while to shrink. One removal may not be enough to make the window valid again.
  • Forgetting to undo the summary when left moves (decrement counts, delete zero-count keys if you compare dictionaries or use their size).
  • Applying it to negative numbers with an exact-sum condition (see above).
  • Off-by-one window length. The window [left, right] has right - left + 1 elements; a fixed window starts producing answers at right = k - 1.

Practice problems by difficulty

Work through these in order; each line names the variant.

ProblemVariantDifficulty
643. Maximum Average Subarray IFixedEasy
1456. Max Vowels in a Substring of Given LengthFixedMedium
3. Longest Substring Without Repeating CharactersLongestMedium
424. Longest Repeating Character ReplacementLongestMedium
1004. Max Consecutive Ones IIILongestMedium
209. Minimum Size Subarray SumShortestMedium
438. Find All Anagrams in a StringFixed + countsMedium
567. Permutation in StringFixed + countsMedium
904. Fruit Into BasketsAt most 2 distinctMedium
992. Subarrays with K Different IntegersCountingHard
76. Minimum Window SubstringShortestHard
239. Sliding Window MaximumFixed + dequeHard

Sliding window problems also appear, with progress tracking, on the Blind 75, LeetCode 150 and DSA sheet. The DSA patterns cheat sheet lists them all in one place.

FAQ

Is sliding window the same as two pointers?

It’s a kind of two pointers where both pointers move in the same direction and the elements between them matter. Classic two pointers starts at both ends of a sorted array and looks only at the pair.

What’s the time complexity of the sliding window algorithm?

O(n) for the pass, because each element is added once and removed at most once. Each add or remove must be O(1) (or O(log n) with a heap or sorted structure, giving O(n log n)).

How do I know if a problem needs a fixed or a variable window?

If the window length is given (k, or len(p) for anagrams), it’s fixed. If the question asks for the longest or shortest range satisfying a condition, it’s variable.

Can sliding window handle negative numbers?

For max/min sum of a fixed k, yes. For “longest/shortest subarray with sum ≥ / = target”, no: negatives break the shrink rule. Use prefix sums (with a monotonic deque for LeetCode 862).

Learn it step by step