Skip to content
Companies
    
DSA Patterns

Learn

Sliding Window

Learn the sliding window pattern: how to recognise it, the fixed and variable-size templates, why it runs in O(n), and the mistakes that cost interviews.

7 min readUpdated 2 Sept 2026

#Arrays#Strings#Two Pointers#O(n)

Almost every "find the best contiguous chunk" problem has a brute-force answer that checks all n² subarrays, and an intended answer that makes one pass. Sliding window is how you get from the first to the second. It is worth learning early because it reappears constantly — the pattern shows up in string problems, in array problems, in rate limiters and in stream processing — and because the recognition step is more valuable than the technique. Once you have decided a problem is a window problem, the code is nearly mechanical.

The idea

Keep two indices, left and right, marking a contiguous range of the input. Move right to take one more element in; move left to drop one from the back. Maintain some summary of what is currently inside — a sum, a count, a frequency map — updating it in O(1) as elements enter and leave rather than recomputing it from scratch.

The whole trick is that last clause. Brute force recomputes the summary for every candidate range, which is what makes it quadratic. The window keeps a running summary and repairs it incrementally, so each element is added once and removed once.

step 1215132sum = 8step 2215132sum = 7+1 −2step 3215132sum = 9+3 −1step 4215132sum = 6+2 −5
Each step adds one value and removes one — the sum is repaired in O(1) instead of recomputed.

Four windows, but ten add/remove operations rather than the twelve additions a recompute-every-window scan would do. At k = 3 that is barely a saving; the gap is the point, though, because the window's cost does not depend on k at all while the naive scan's does.

When to reach for it

Sliding window applies when three things are true. If any one fails, it is the wrong tool and forcing it produces subtly wrong code.

  1. The answer is a contiguous run — a subarray or a substring, not a subsequence.

The moment a problem lets you skip elements, the window has nothing to slide over and you are probably looking at dynamic programming instead.

  1. You are optimising or counting over all such runs — longest, shortest, maximum

sum, number of runs satisfying some property.

  1. The property is monotone as the window grows. Adding an element can only push

the window further from valid (or further past a threshold), and removing one can only push it back toward valid. This is what makes it safe to shrink from the left and never look back.

That third condition is the one people skip, and it is the one that breaks. "Longest subarray with sum at most K" is monotone when all values are non-negative — adding an element only increases the sum. Introduce negative numbers and it is not: a window that is too big can become valid again by growing, so shrinking from the left throws away answers. That problem needs prefix sums with a hash map, not a window.

Phrases that should make you think "window": contiguous, substring, subarray,

consecutive, of size k, at most k distinct, longest/shortest ... such that.

Fixed-size windows

The easy half. The window is always exactly k wide, so both ends move in lockstep and there is no shrink logic to get wrong. Build the first window, then slide it.

def max_sum_of_size_k(nums, k):
    window = sum(nums[:k])
    best = window
    for right in range(k, len(nums)):
        window += nums[right] - nums[right - k]   # add one, drop one
        best = max(best, window)
    return best

The pattern generalises past sums: swap the running total for a frequency counter and the same skeleton answers "does any window of length k contain all distinct characters", "find all anagrams of p in s", and every other fixed-width question.

Variable-size windows: the template

The interesting half, and the one worth memorising as a shape rather than as code. The window grows by default and shrinks only when it has to.

def longest_valid(nums):
    left = 0
    best = 0
    state = init()

    for right in range(len(nums)):
        add(state, nums[right])          # 1. take the new element in

        while not valid(state):          # 2. repair from the left
            remove(state, nums[left])
            left += 1

        best = max(best, right - left + 1)   # 3. every window here is valid

    return best

Three lines of intent, and every variable-size window problem is a choice of what goes in state, valid and the update at step 3:

Questionstatevalid(state)
Longest substring without repeatslast index of each charno char appears twice
Longest with at most K distinctchar → count maplen(map) <= K
Smallest subarray with sum ≥ targetrunning sum(inverted — see below)
Longest with at most K zeros after flippingcount of zeroszeros <= K

Note the direction. For longest, the while restores validity and you record after it, because the window is valid exactly when the loop exits. For shortest, it flips: the while condition becomes "still valid", and you record inside the loop before each removal, because you want the smallest window that still qualifies.

def min_subarray_len(target, nums):
    left = total = 0
    best = float("inf")

    for right, value in enumerate(nums):
        total += value
        while total >= target:               # while STILL valid
            best = min(best, right - left + 1)   # record before shrinking
            total -= nums[left]
            left += 1

    return 0 if best == float("inf") else best

Getting the record-point wrong is the single most common bug in this pattern, and it produces answers that are off by one in a way that passes the sample case.

A worked example

Longest substring without repeating characters — "abcabcbb", expected answer 3.

def length_of_longest_substring(s):
    seen = {}          # char -> most recent index
    left = best = 0

    for right, ch in enumerate(s):
        if ch in seen and seen[ch] >= left:
            left = seen[ch] + 1     # jump past the earlier copy
        seen[ch] = right
        best = max(best, right - left + 1)

    return best

Traced:

rightchleftwindowbest
0a0a1
1b0ab2
2c0abc3
3a1bca3
4b2cab3
5c3abc3
6b5cb3
7b7b3

The seen[ch] >= left guard matters. Without it, a character last seen before the current window drags left backwards, and the window stops being a window. This is the version of the bug interviewers watch for, because the naive code still passes "abcabcbb" and fails "abba".

The counting variant

"Count subarrays with exactly K distinct values" looks like a window problem and resists the template — exactly-K is not monotone, so there is no clean shrink rule.

The standard move is to solve the monotone version and subtract:

exactly(K) = atMost(K) - atMost(K - 1)

atMost(K) is a window problem: grow, shrink while there are more than K distinct, and add right - left + 1 to the count at each step — that being the number of valid windows ending at right. Run it twice.

Recognising that a hard problem is two easy window passes in a trench coat is worth more than any single template here, and it generalises: exactly-K sums, exactly-K odd numbers, exactly-K vowels all decompose the same way.

Why it is O(n)

Expect to be asked, because the loop looks nested. The argument is amortisation: right advances exactly n times across the whole run, and left only ever advances, never resets, so it also moves at most n times in total. The inner while may run many iterations on one step of right and zero on the next, but summed over the whole input it does at most n removals. Total work is O(n), not O(n²) — 2n pointer moves and O(1) work each.

Space is O(1) for sum-based windows and O(k) — or O(alphabet) — when the state is a frequency map.

Mistakes that cost the round

  • Recomputing the state inside the loop. sum(nums[left:right+1]) in the body

quietly restores the quadratic runtime you came here to avoid, and it is easy to miss because the code still looks like a window.

  • Recording the answer in the wrong place. Longest records after the shrink loop;

shortest records inside it. See above.

  • Assuming monotonicity. Negative numbers, or a validity condition that can flip

back and forth as the window grows, both break the pattern. Say this out loud in an interview — noticing the precondition reads as much stronger than reciting a template.

  • Off-by-one in the width. It is right - left + 1 when both ends are inclusive.

Pick a convention and hold it for the whole function.

  • Letting `left` move backwards. Only in the index-jumping variant, and only when

the >= left guard is missing.

What to drill

Work these in order — each adds exactly one idea to the last:

  1. Maximum Average Subarray I — fixed window, nothing else.
  2. Longest Substring Without Repeating Characters — the canonical variable window.
  3. Minimum Size Subarray Sum — the shortest-variant flip.
  4. Permutation in String — fixed window over a frequency map.
  5. Longest Repeating Character Replacement — validity you have to derive.
  6. Sliding Window Maximum — window plus a monotonic deque; the step up.
  7. Minimum Window Substring — the hard one, and the one that gets asked.

Six of those seven are on the 22 DSA Patterns sheet, which tracks your progress through them as you go.

Frequently asked

What is the sliding window pattern?

A technique for problems about contiguous subarrays or substrings. Two pointers mark the ends of a range; you maintain a running summary of what is inside the range and update it in O(1) as elements enter and leave, instead of recomputing it for every candidate range. That turns an O(n²) scan into a single O(n) pass.

When should I use sliding window instead of two pointers?

Sliding window is a two-pointer technique — the distinction is that both pointers move in the same direction over a contiguous range you are tracking state for. Classic two pointers usually means one pointer at each end of a sorted array converging inward, as in 3Sum or Container With Most Water, with no window state to maintain.

Why is the sliding window O(n) when it has a nested loop?

Because left only ever moves forward and never resets. Over the whole run, right advances n times and left advances at most n times, so the inner loop does at most n removals in total no matter how it is distributed. That is 2n pointer moves with O(1) work each, so O(n) overall.

Does sliding window work with negative numbers?

Not for sum-threshold problems. The pattern relies on adding an element only pushing the window in one direction; with negatives, a window whose sum is too large can become valid again by growing, so shrinking from the left discards valid answers. Use prefix sums with a hash map instead. Windows keyed on counts or distinct elements are unaffected.

How do I count subarrays with exactly K distinct elements?

Solve it as atMost(K) - atMost(K - 1). Exactly-K is not monotone so it has no clean shrink rule, but at-most-K is a textbook variable window, and the difference of the two counts gives exactly K. The same decomposition works for exactly-K sums, odds or vowels.

Related

Two Pointers

One pointer at each end, converging. Turns the O(n²) pair search into a single sorted pass.

Monotonic Stack

A stack kept in sorted order answers every 'next greater element' question in one O(n) pass.

Prefix Sum

Precompute running totals once, answer any range query in O(1) — and count target-sum subarrays in one pass.