The Sliding Window Pattern: Template & When to Use It

The sliding window pattern turns an O(n·k) or O(n²) scan over contiguous subarrays or substrings into a single O(n) pass by maintaining a moving “window” [left, right] and updating a running summary as the window slides instead of recomputing it from scratch. This page recaps when to reach for it and gives templates for both window types.

For the full topic treatment, see sliding window: introduction.

The signal: when to recognize it

The pattern almost always involves a contiguous run of elements. Look for these phrases:

“Subarray / substring” (contiguous) — not “subsequence” (which can skip elements; that’s usually DP).
“Longest / shortest / maximum / minimum” run satisfying a condition.
“At most k distinct / exactly k / sum equals / sum at least.”
A fixed window size is given (“every window of size k”).

For beginners: The whole trick is don’t recompute. When the window moves right by one, you add one new element’s contribution and remove one old element’s — O(1) per step instead of rescanning the window.

Template: fixed-size window

When the window size k is given, slide a window of exactly k and track its summary (here, the maximum sum of any window of size k).

#include <vector>
#include <algorithm>
// Fixed window: maximum sum of any contiguous subarray of size k.
long maxSumWindow(const std::vector<int>& a, int k) {
    long windowSum = 0;
    for (int i = 0; i < k; i++) windowSum += a[i];   // first window
    long best = windowSum;
    for (int right = k; right < (int)a.size(); right++) {
        windowSum += a[right] - a[right - k];        // slide: add new, drop old
        best = std::max(best, windowSum);
    }
    return best;
}

// Fixed window: maximum sum of any contiguous subarray of size k.
long maxSumWindow(int[] a, int k) {
    long windowSum = 0;
    for (int i = 0; i < k; i++) windowSum += a[i];   // first window
    long best = windowSum;
    for (int right = k; right < a.length; right++) {
        windowSum += a[right] - a[right - k];        // slide: add new, drop old
        best = Math.max(best, windowSum);
    }
    return best;
}

// Fixed window: maximum sum of any contiguous subarray of size k.
function maxSumWindow(a, k) {
  let windowSum = 0;
  for (let i = 0; i < k; i++) windowSum += a[i];     // first window
  let best = windowSum;
  for (let right = k; right < a.length; right++) {
    windowSum += a[right] - a[right - k];            // slide: add new, drop old
    best = Math.max(best, windowSum);
  }
  return best;
}

# Fixed window: maximum sum of any contiguous subarray of size k.
def max_sum_window(a, k):
    window_sum = sum(a[:k])          # first window
    best = window_sum
    for right in range(k, len(a)):
        window_sum += a[right] - a[right - k]   # slide: add new, drop old
        best = max(best, window_sum)
    return best

Template: variable-size window

When the size isn’t fixed, grow the window by moving right, and shrink from left whenever the window breaks a constraint. This finds the longest substring with no repeated characters.

#include <string>
#include <unordered_map>
#include <algorithm>
// Variable window: length of the longest substring without repeating characters.
int longestUnique(const std::string& s) {
    std::unordered_map<char, int> lastSeen;
    int left = 0, best = 0;
    for (int right = 0; right < (int)s.size(); right++) {
        char c = s[right];
        if (lastSeen.count(c) && lastSeen[c] >= left)
            left = lastSeen[c] + 1;        // shrink past the duplicate
        lastSeen[c] = right;
        best = std::max(best, right - left + 1);
    }
    return best;
}

import java.util.HashMap;
import java.util.Map;
// Variable window: length of the longest substring without repeating characters.
int longestUnique(String s) {
    Map<Character, Integer> lastSeen = new HashMap<>();
    int left = 0, best = 0;
    for (int right = 0; right < s.length(); right++) {
        char c = s.charAt(right);
        if (lastSeen.containsKey(c) && lastSeen.get(c) >= left)
            left = lastSeen.get(c) + 1;    // shrink past the duplicate
        lastSeen.put(c, right);
        best = Math.max(best, right - left + 1);
    }
    return best;
}

// Variable window: length of the longest substring without repeating characters.
function longestUnique(s) {
  const lastSeen = new Map();
  let left = 0, best = 0;
  for (let right = 0; right < s.length; right++) {
    const c = s[right];
    if (lastSeen.has(c) && lastSeen.get(c) >= left)
      left = lastSeen.get(c) + 1;          // shrink past the duplicate
    lastSeen.set(c, right);
    best = Math.max(best, right - left + 1);
  }
  return best;
}

# Variable window: length of the longest substring without repeating characters.
def longest_unique(s):
    last_seen = {}
    left = best = 0
    for right, c in enumerate(s):
        if c in last_seen and last_seen[c] >= left:
            left = last_seen[c] + 1     # shrink past the duplicate
        last_seen[c] = right
        best = max(best, right - left + 1)
    return best

Complexity

Both templates are O(n) time: right advances n times, and left only ever advances (it never moves backward), so total pointer movement is bounded by 2n. Space is O(1) for the fixed-sum version and O(k) (the distinct elements in the window) for the variable version that tracks counts.

Common pitfalls

Using it on non-contiguous problems. “Subsequence” is not a window — that’s usually dynamic programming.
Shrinking with if vs while. For “at most k” constraints you often need a while loop to shrink until the window is valid again.
Stale running summary. When you move left, you must subtract the leaving element’s contribution.

Going deeper: Prefix sums solve some “sum equals k” window problems even when values can be negative — a case the shrink-on-overflow window can’t handle.

Practice

Drill it in the sliding window exercises. Compare with the two-pointers pattern: both walk two indices, but a window keeps everything between them as the answer candidate.