Overview

Many problems ask for the best contiguous subarray or substring that satisfies a condition. Checking every one is O(n²) or worse. A sliding window keeps a single range [left, right], grows it by moving right, and shrinks it by moving left whenever the condition breaks. Because each element enters and leaves the window at most once, the total work is O(n).

The art is choosing the window state: a running sum, a count of each character, the number of distinct values. The state must be cheap to update when one element enters or leaves. If you can do that, the problem is probably a sliding window.

Key concepts

Tick a concept once you can explain it in your own words without notes.

Complexity cheat sheet

OperationCost
All subarrays, brute forceO(n²) windows, often O(n³) total
Sliding windowO(n) time
Window with frequency mapO(n) time, O(alphabet) space

Patterns to recognise

Fixed window

Use it for: Problems that say "subarray of size k".

Pre-fill k elements, then slide one step at a time.

Longest valid window

Use it for: Longest substring without repeats, with at most k replacements, fruit into baskets.

Expand; shrink only until valid again; record right − left + 1.

Shortest covering window

Use it for: Minimum window substring, minimum size subarray sum.

Expand until valid; then shrink as far as possible while recording the length.

Code template

Longest substring without repeating characters
def length_of_longest_substring(s):
    last_seen = {}
    left = best = 0
    for right, ch in enumerate(s):
        if ch in last_seen and last_seen[ch] >= left:
            left = last_seen[ch] + 1          # jump past the repeat
        last_seen[ch] = right
        best = max(best, right - left + 1)
    return best

Common mistakes

  • Forgetting to update the window state when the left edge moves.
  • Window length is right − left + 1, not right − left.
  • Applying a shrinking window to arrays with negative numbers.

Quick check

Three questions on Sliding Window. Get all three right to earn +15 XP.

  1. A sliding window turns many O(n x k) brute-force scans into:

  2. In a variable-size window, when do you move the left edge forward?

  3. Why can a sliding window fail on "subarray sum equals k" when numbers can be negative?

Challenges

Ordered from easiest to hardest. Solve them on LeetCode, then tick them off here. Know every concept and solve 3 to clear the level.

Stuck on Sliding Window?Ask Orbi for a hint, a fresh explanation or a review of your code.

Ask the tutor