← All patterns

Sliding Window

Maintain a contiguous window over an array or string, expanding and shrinking to preserve an invariant. Powers most 'longest / shortest / count substring with property X' problems, often turning O(n²) brute force into O(n).

19 problems 3 Easy 9 Medium 7 Hard

Sliding window maintains a contiguous range and updates its state incrementally — adding to the right edge, removing from the left — rather than recomputing from scratch. Variants: fixed-size (rolling sum / average over a window of k), variable-size (shrink-on-invalid until the window is valid again), and at-most-k counting (`exactly = atMost(K) - atMost(K-1)`).

The pattern is the workhorse for 'longest / shortest / count substring with property X' — over half the medium-difficulty string problems use it.

When to reach for this pattern

  • Longest or shortest substring/subarray with a property
  • Count subarrays / substrings satisfying a constraint
  • Fixed window of size K computing an aggregate (average, max, sum)
  • Anagram or permutation match within a stream

Canonical template 

// variable-size, shrink-on-invalid
int left = 0, best = 0;
for (int right = 0; right < (int)n; ++right) {
    addToWindow(arr[right]);
    while (!valid()) removeFromWindow(arr[left++]);
    best = max(best, right - left + 1);
}

// fixed-size rolling sum
long long sum = 0;
for (int i = 0; i < k; ++i) sum += arr[i];
long long best = sum;
for (int i = k; i < (int)n; ++i) {
    sum += arr[i] - arr[i - k];
    best = max(best, sum);
}

C++ · adapt the names and types to your problem.

Common pitfalls

  • Window length is right - left + 1, not right - left
  • Forgetting to update window state on the shrink path — asymmetric add/remove
  • Sliding window requires monotone state: works with positives, breaks on signed sums unless you adjust
  • Confusing 'exactly K distinct' (use atMost(K) − atMost(K−1)) with 'at most K' (direct shrink)

Related patterns

Two Pointers Hash Maps Tracking Patterns

Problems (19)

Search ESC

Keyboard shortcuts

Shortcuts are disabled while typing in inputs.