Sliding Window Pattern in DSA: When and How to Use It

You’re given a long array and asked for the best contiguous stretch of it: the highest sum of 5 numbers, the longest substring with no repeats, the shortest run that adds up to a target. The first solution that comes to mind recomputes every stretch from scratch, and it times out.

This guide teaches the sliding window pattern the way you’d use it in an interview. You’ll see why brute force fails, how to recognize a window problem from its wording, a dry-run trace of both window types, reusable templates in Python and C++, five variations, 10 practice problems in order, and the mistakes that quietly break correct-looking code. Complexity terms are explained in our guide to time and space complexity if you need a refresher.

Phase 1: The Problem (Recomputing What You Already Know)

Question: given an array of n integers and a number k, find the maximum sum of any k consecutive elements.

The brute force sums every window from scratch:

def max_sum_brute(nums, k):
    best = float("-inf")
    for start in range(len(nums) - k + 1):
        best = max(best, sum(nums[start:start + k]))
    return best

There are n - k + 1 windows and each costs k additions, so the total is O(n·k). With n = 1,000,000 and k = 500,000, that’s roughly 2.5 × 10¹¹ additions. It will not finish.

The waste is obvious once you look at two neighboring windows. Moving from the window [0..k-1] to [1..k], all but two elements are identical. You add one new number and drop one old number. Recomputing the other k - 1 is pure repetition.

The same waste shows up in string problems. “Longest substring without repeating characters” has a brute force that checks every substring for duplicates, which is O(n²) substrings times an O(n) check. Both problems collapse to O(n) once you stop throwing away the work done on the previous window.

Phase 2: The Pattern

The idea

A sliding window is a contiguous range [l, r] over an array or string, together with a small piece of state describing what’s inside it (a sum, a character count, a set). You move the right edge forward to bring in a new element, and move the left edge forward to drop an old one. Each move updates the state in O(1) instead of recomputing it.

Analogy: a magnifying glass sliding along a line of text, with a tally sheet beside it. You never re-read the words under the lens. You add a tick for the word entering on the right and erase a tick for the word leaving on the left. The tally sheet is your state, and keeping it cheap to update is the whole game.

Two flavors

Fixed-size window. The window length k is given. Slide it one step at a time. Use it for “any subarray of length k“.

Variable-size window. The length changes. You expand r until a condition is met or broken, then shrink l to restore it. It splits into two sub-types:

• Longest valid window: expand freely, and shrink only while the window is invalid. Record the answer after restoring validity.
• Shortest valid window: expand until the window is valid, then shrink while it stays valid, recording the answer on each shrink.

Trigger phrases

• “longest / shortest / maximum / minimum subarray or substring such that …”
• “contiguous”, “consecutive”, “of size k“
• “at most k distinct …”, “at most k replacements / flips”
• “contains all characters of …”, “is a permutation or anagram of …”
• “sum at least / at most target” with non-negative numbers

The decision in one picture

What most tutorials get wrong: they present sliding window as “two pointers that move right,” and never state the condition that makes it correct. A variable window works only if the condition is monotone: once a window is invalid, making it bigger can’t fix it, and once it’s valid, making it smaller can’t break the “validity” you’re shrinking toward. For “sum at least target” with non-negative numbers, that holds. With negative numbers it doesn’t: adding an element can lower the sum, so shrinking from the left no longer tells you anything reliable. That’s why “subarray sum equals k” with negatives is a prefix-sum-and-hash-map problem, not a sliding window. Also, the O(n) claim isn’t obvious when you see a while loop inside a for loop. It holds because each element enters the window once and leaves at most once, so the total shrink steps across the whole run are at most n.

The relationship to our two pointers vs fast and slow pointers guide is worth knowing. A sliding window is a same-direction pair of pointers where the region between them carries state. The difference from plain reader/writer pointers is that the pointers’ region is the thing you’re measuring.

Phase 3: Step-by-Step Walkthrough

Trace 1: Fixed window

Array [2, 1, 5, 1, 3, 2], k = 3. Compute the first window directly, then slide.

Answer: 9. Each slide costs exactly two operations (sum += added - removed), regardless of k.

Trace 2: Variable window, longest substring without repeating characters

String "abcbda". State: a count of each character in the window. Rule: while the new character’s count is above 1, drop characters from the left.

Answer: 4. At r = 3 the shrink loop ran twice, which is exactly why it must be a while, not an if.

Phase 4: Code Templates

Pure Python 3 (standard library only) and C++17.

Template A: Fixed window

def max_sum_k(nums, k):
    if k <= 0 or len(nums) < k:
        return None
    window = sum(nums[:k])
    best = window
    for r in range(k, len(nums)):
        window += nums[r] - nums[r - k]      # add the new element, drop the old one
        best = max(best, window)
    return best                              # O(n) time, O(1) space

What problem it solves: any question about all windows of a known length, such as max sum, max average, or whether a window contains duplicates.

Key parts: build the first window once, then update in O(1). The element leaving is nums[r - k].

Production notes: running sums over floats accumulate rounding error across millions of updates. For long streams, periodically recompute from scratch or use integer arithmetic.

Template B: Variable window, longest valid

def longest_unique(s):
    count = {}
    l = best = 0
    for r, ch in enumerate(s):
        count[ch] = count.get(ch, 0) + 1
        while count[ch] > 1:                 # window invalid: shrink until valid again
            count[s[l]] -= 1
            l += 1
        best = max(best, r - l + 1)          # record when valid
    return best                              # O(n) time, O(min(n, alphabet)) space

#include <algorithm>
#include <string>
#include <vector>
using namespace std;

int longestUnique(const string& s) {
    vector<int> cnt(256, 0);                 // assumes single-byte characters
    int l = 0, best = 0;
    for (int r = 0; r < (int)s.size(); ++r) {
        unsigned char c = s[r];
        ++cnt[c];
        while (cnt[c] > 1) {
            --cnt[(unsigned char)s[l]];
            ++l;
        }
        best = max(best, r - l + 1);
    }
    return best;                             // O(n) time, O(1) space
}

What problem it solves: the longest range that satisfies a constraint you can check from a small state.

Key parts: expand with the for, restore validity with the while, record the answer after the window is valid.

Production notes: the Python dictionary handles any Unicode character, but the C++ array above assumes single-byte characters. For UTF-8 text, decide whether you’re counting bytes or code points before choosing the data structure.

Template C: Variable window, shortest valid

def min_len_at_least(target, nums):          # nums must be non-negative
    l = total = 0
    best = float("inf")
    for r, x in enumerate(nums):
        total += x
        while total >= target:               # window valid: try to shrink
            best = min(best, r - l + 1)      # record INSIDE the loop
            total -= nums[l]
            l += 1
    return 0 if best == float("inf") else best   # O(n) time, O(1) space

What problem it solves: the smallest range that reaches a threshold.

Key parts: the answer is recorded inside the shrink loop, because validity is what you’re preserving while shrinking.

Production notes: this relies on non-negative values. One negative number breaks the monotonicity and the result can be wrong without any error.

Template D: Monotonic deque for window maximum

from collections import deque

def max_sliding_window(nums, k):
    dq, out = deque(), []                    # dq holds indices; values decrease front to back
    for i, x in enumerate(nums):
        while dq and nums[dq[-1]] <= x:
            dq.pop()                         # smaller elements can never be a max again
        dq.append(i)
        if dq[0] <= i - k:
            dq.popleft()                     # front index has left the window
        if i >= k - 1:
            out.append(nums[dq[0]])
    return out                               # O(n) time, O(k) space

What problem it solves: max or min over every window when a running sum won’t do, because “max” can’t be updated by subtraction.

Key parts: the deque stores indices in decreasing value order, so the front is always the current maximum. Each index is pushed and popped at most once.

Production notes: this is the technique behind streaming min/max over a time window in metrics and monitoring code. Memory is bounded by the window size, which matters on long-lived streams.

Phase 5: Variations

1. Fixed window, aggregate value. Template A. Examples: max average of k elements, or “does any window of size k contain a duplicate?” (keep a set of the window’s elements).

2. Longest window with at most K distinct items. Same shape as Template B, with the invalid condition being len(count) > K. Remove a key when its count hits zero, or len(count) will lie.

def longest_k_distinct(s, k):
    count, l, best = {}, 0, 0
    for r, ch in enumerate(s):
        count[ch] = count.get(ch, 0) + 1
        while len(count) > k:
            count[s[l]] -= 1
            if count[s[l]] == 0:
                del count[s[l]]
            l += 1
        best = max(best, r - l + 1)
    return best

3. Shortest window that contains everything required. Template C’s shape, with the state being “how many required characters are still missing”. Minimum Window Substring is the standard example.

4. “Exactly K” via “at most”. Counting windows with exactly K distinct values is awkward directly. Count windows with at most K, subtract the count with at most K - 1.

def count_at_most(nums, k):
    count, l, total = {}, 0, 0
    for r, x in enumerate(nums):
        count[x] = count.get(x, 0) + 1
        while len(count) > k:
            count[nums[l]] -= 1
            if count[nums[l]] == 0:
                del count[nums[l]]
            l += 1
        total += r - l + 1                   # all valid windows ending at r
    return total

def count_exactly_k(nums, k):
    return count_at_most(nums, k) - count_at_most(nums, k - 1)

5. Window max or min. Template D, when the aggregate can’t be maintained by add-and-subtract.

Phase 6: Practice Problems (Easy to Hard)

Problem numbers are LeetCode’s.

If you finish this set and want the pointer techniques that don’t use a window, continue with the two pointers guide.

Phase 7: Common Mistakes and Edge Cases

• Window length off by one. The length of [l, r] is r - l + 1, not r - l.
• Wrong first window. In a fixed window, the loop for sliding starts at index k, and the element leaving is nums[r - k]. Test with k = 1 and k = n.
• k larger than the array, or k <= 0. Decide what to return and handle it before the loop.
• if instead of while for shrinking. One removal often isn’t enough, as the abcbda trace showed.
• Recording the answer at the wrong time. For longest, record after the window is valid. For shortest, record inside the shrink loop.
• Negative numbers. The shrink logic assumes monotonicity. With negatives, use prefix sums and a hash map.
• Stale keys in a count map. If you test len(count) for distinct items, delete a key when its count reaches zero.
• Empty input. An empty string or array should return 0 (or your problem’s equivalent) without special cases creeping into the loop.
• Overflow. In C++ and Java, sums of many int values can overflow. Use long long.
• Duplicates in the pattern. In window-contains-all-characters problems, track counts, not just a set. Needing two as is different from needing one.
• Character set assumptions. A 256-element array is wrong for Unicode input. Use a map when you can’t bound the alphabet.

Phase 8: Where This Appears in Real Systems

Rate limiting. A “sliding window log” limiter keeps the timestamps of recent requests, drops those older than the window, and allows a request only if fewer than the limit remain. That is the same add-on-the-right, evict-on-the-left idea, with a deque of timestamps as the window.

from collections import deque

class SlidingLogLimiter:
    def __init__(self, limit, window_seconds):
        self.limit = limit
        self.window = window_seconds
        self.times = deque()

    def allow(self, now):
        while self.times and self.times[0] <= now - self.window:
            self.times.popleft()             # evict expired timestamps
        if len(self.times) < self.limit:
            self.times.append(now)
            return True
        return False

The trade-off is memory: the log stores up to limit timestamps per client. Cloudflare has publicly described a cheaper approximation, the sliding window counter, which keeps two fixed-window counts and weights the previous one by how far into the current window you are. Secondary write-ups report very low error against the exact log, but treat that figure as something to confirm against Cloudflare’s own post (see fact-check notes).

Streams and conversation history. Networking protocols such as TCP use a window to bound how much unacknowledged data can be in flight, and many LLM applications keep only the most recent messages of a conversation. Both are window-shaped. See how AI agent memory systems work for how that trimming fits into larger memory designs.

If you’re building toward interviews, sliding window is one of the first patterns screeners test. It sits early in the plan in our AI engineer career roadmap.

Key Takeaways

• A sliding window turns an O(n·k) or O(n²) recomputation into O(n) by updating a small state as elements enter and leave.
• Pick fixed when the length is given, variable when you’re optimizing the length.
• For longest valid, shrink while invalid and record after. For shortest valid, shrink while valid and record inside the loop.
• The pattern’s correctness rests on monotonicity. Negative numbers break “sum at least target“, so switch to prefix sums.
• The nested loop is still O(n) because each element enters and leaves at most once.
• Use a monotonic deque when you need the window’s max or min.
• “Exactly K” is usually atMost(K) - atMost(K - 1).

FAQ

When should I use the sliding window technique? Use it when the question is about a contiguous subarray or substring and you can update a small state as the window moves. Phrases like “longest substring”, “at most K distinct”, or “subarray of size K” are strong signals.

What is the difference between sliding window and two pointers? Sliding window is a special case of same-direction two pointers where the range between the pointers carries state, such as a sum or a count map. General two pointers also covers converging pointers on sorted data, which don’t maintain a window.

Why is a sliding window O(n) when it has a nested loop? Because the left pointer only moves forward. Across the whole run, each element is added once and removed at most once, so the total work in the while loop is bounded by n.

Why doesn’t sliding window work with negative numbers? Shrinking a window only makes sense if removing elements moves the sum in a predictable direction. With negatives, adding or removing an element can push the sum either way, so you can’t decide which edge to move. Use prefix sums with a hash map instead.

How do I count subarrays with exactly K of something? Count the subarrays with at most K, then subtract the count with at most K – 1. Each is a standard variable-window computation.