Two pointers and sliding window

What this chapter covers

A huge number of array and string problems have an obvious O(n²) solution — for every starting point, scan forward — and a much better O(n) one that most people miss at first. The technique that unlocks the linear version is two pointers: instead of a nested loop, move two indices through the data and maintain the window between them incrementally, updating only what changes as the window slides rather than recomputing it from scratch. It's the same insight as the rolling hash, generalized into a design pattern. This chapter covers the three shapes it takes — a variable-size sliding window (longest substring with no repeated character), the two-pointer walk from both ends (a pair summing to a target in a sorted array), and a fixed-size sliding window (maximum sum of k consecutive elements) — and shows the payoff: on the longest-unique-substring problem, the sliding window does 400 times less work than the brute force at length 800, because each index only ever moves forward.

A bit of history

Two pointers and sliding window don't have a single inventor or a famous origin — they're folklore techniques, the kind of idea that gets rediscovered constantly because it's the natural optimization once you notice a nested loop is redoing work. Their rise to prominence is more about pedagogy than history: as algorithmic interviewing became standardized in the 2000s and 2010s, these patterns became among the most taught and tested, precisely because they capture a transferable insight — recognizing when a quadratic scan hides a linear structure. The underlying principle is old and deep, though: it's the same amortization idea that makes KMP's scan linear (a pointer that only advances), the rolling hash O(1) per slide (update, don't recompute), and the dynamic array's appends O(1) (occasional cost spread over many operations). Sliding window is that principle applied to the ubiquitous "examine every contiguous range" problem, and its value is as much in training the eye to see the linear solution as in the code itself.

The intuition

Take the flagship problem: the longest substring with no repeated character. In abcabcbb, the answer is abc, length 3. The brute force tries every starting position and extends until it hits a repeat — O(n²), and it re-examines the same characters over and over across overlapping starts. The sliding window does it in one pass with two pointers marking the current window [left, right]. Advance right one character at a time, extending the window. The window's invariant is "no repeated character inside it." When the new character at right is one that's already in the current window, the invariant would break — so jump left forward to just past that character's previous occurrence, which restores the invariant by dropping the stale part of the window. Track the largest window seen. Both pointers only ever move forward, never back, so the total work is O(n) even though the window grows and shrinks.

The other two shapes share the "two indices, incremental state" idea in different geometries. The two-pointer walk works on a sorted array: to find a pair summing to a target, start one pointer at each end. If the current sum is too small, the only way to increase it is to move the low pointer right (toward larger values); if too large, move the high pointer left. Each move eliminates one value from consideration, so the pair is found (or ruled out) in O(n) — no nested loop, no hash set. The fixed-size window slides a constant-width window across the data to compute something like the maximum sum of k consecutive elements: compute the first window's sum once, then for each slide add the entering element and subtract the leaving one, O(1) per step instead of re-summing k elements. All three replace a nested loop with a sweep, and the common trick is that the window's state (the character set, the running sum, the pointer positions) is carried across the slide and updated cheaply, never rebuilt.

Complexity: how it scales

The sliding window is O(n): the right pointer visits each element once, and the left pointer only moves forward, so their combined movement is at most 2n — an amortized argument identical to KMP's. The brute force is O(n²) in the worst case (a string of all-distinct characters, where every start extends the full length). The face-off counts operations on exactly that worst case as the input grows:

On a log-log plot the brute-force line has slope 2 (quadratic) and the sliding-window line slope 1 (linear) — they diverge without bound. At length 800, the sliding window did 800 operations (one per character) while the brute force did about 320,000 — a 400-fold difference, and the ratio grows linearly with the input, so at length 8,000 it would be 4,000-fold. This is the recurring shape of these techniques: they don't shave a constant factor, they drop a whole factor of n, turning a scan that chokes on large inputs into one that sails through. The window's incremental state is what buys it — the brute force re-reads overlapping regions the window handles once.

What it's good at, what it isn't

Two-pointer and sliding-window techniques are the right tool for problems about contiguous ranges (subarrays, substrings) or pairs/triples in sorted data, whenever the target property can be maintained incrementally as the window moves. The canonical uses: longest/shortest subarray or substring satisfying a condition (no repeats, at most k distinct, sum ≥ target, containing a required set), pair-and-triple-sum problems in sorted arrays (two-sum, three-sum, closest pair), fixed-window statistics (moving averages, max/min over a window), merging sorted sequences, and partitioning (the quicksort partition and Dutch-flag are two-pointer). They turn a great many O(n²) brute forces into O(n) or O(n log n) (with a sort), which is why they're such staples.

Where they don't apply is when the property isn't monotone in the window — when shrinking from the left might later require re-expanding, the simple sweep gives wrong answers, and you need a heavier structure (a monotonic deque, prefix sums with a hash map, a balanced tree). Subarray-sum-equals-target with negative numbers is the classic trap: the window sum isn't monotone as you extend, so the two-pointer approach fails and you need a prefix-sum hash map instead. Two-pointer-from-both-ends requires sorted input, so it costs an O(n log n) sort if the data isn't already ordered. And these are techniques for linear structure, not a substitute for the other paradigms — problems needing global search (backtracking) or overlapping-subproblem optimization (DP) aren't sliding-window shaped. The precondition — monotone, incrementally-maintainable window state — is what to check before reaching for them.

The data, or the inputs

The face-off counts operations for the longest-unique-substring problem — the sliding window against the nested-loop brute force — on all-distinct inputs (the brute force's O(n²) worst case) as length grows. Correctness is checked on thousands of random cases across all three techniques: the sliding window's length must match the brute force and its returned substring must be genuinely repeat-free and present in the string; the two-pointer pair-sum must agree with the brute-force pair search (finding a valid pair exactly when one exists); and the fixed-window maximum must match re-summing every window. The animation slides the window over abcabcbb, showing the left and right pointers and the left-jump each time a repeated character enters.

Build it, one function at a time

The variable-size sliding window — longest substring with no repeat:

def longest_unique_substring(s, trace=None):
    """Longest substring with no repeated character, in one pass. `last` remembers each character's
    most recent index. Extend the window's right edge over every character; when the new character
    was already seen INSIDE the current window, jump the left edge just past that previous
    occurrence (shrinking the window to stay duplicate-free). Track the largest window. O(n): each
    index moves forward only, never back. Returns (length, the substring)."""
    last = {}
    left = 0
    best_len, best_l = 0, 0
    for right, ch in enumerate(s):
        if ch in last and last[ch] >= left:
            left = last[ch] + 1                   # contract: skip past the duplicate
        last[ch] = right
        if right - left + 1 > best_len:
            best_len, best_l = right - left + 1, left
        if trace is not None:
            trace.append((left, right, best_len))
    return best_len, s[best_l:best_l + best_len]

The two-pointer walk from both ends — a pair summing to a target in sorted data:

def two_sum_sorted(nums, target):
    """In a SORTED array, find two values summing to `target`, using two pointers from the ends. If
    the current sum is too small, move the left pointer right (only larger values remain that way);
    if too large, move the right pointer left. Each step discards one candidate, so it's O(n) — no
    nested loop, no hash set. Returns the (i, j) indices, or None."""
    lo, hi = 0, len(nums) - 1
    while lo < hi:
        s = nums[lo] + nums[hi]
        if s == target:
            return (lo, hi)
        if s < target:
            lo += 1                               # need a bigger sum → raise the low end
        else:
            hi -= 1                               # need a smaller sum → lower the high end
    return None

The fixed-size sliding window — maximum sum of k consecutive elements, O(1) per slide:

def max_window_sum(nums, k):
    """Maximum sum of any k consecutive elements, by sliding a fixed-width window: compute the first
    window's sum, then for each step add the entering element and subtract the leaving one — O(1)
    per slide instead of re-summing k elements. O(n) total. Returns the best sum."""
    if k > len(nums) or k <= 0:
        return None
    window = sum(nums[:k])
    best = window
    for i in range(k, len(nums)):
        window += nums[i] - nums[i - k]           # roll: +entering, -leaving
        best = max(best, window)
    return best

Watch it work

Here's the sliding window finding the longest repeat-free substring of abcabcbb. The green cell is the left edge of the window, orange is the right edge, and the blue cells between them are the current window. Watch the right pointer march forward, extending the window: a, ab, abc — length 3. Then the next character is another a, which is already in the window (it flashes red) — so the left pointer jumps forward past that old a, shrinking the window to keep it repeat-free. The window slides along, expanding when it can and contracting when a duplicate forces it, never moving either pointer backward. The largest window it ever holds — abc, length 3 — is the answer. Every character is visited once by the right pointer and at most once by the left, which is why the whole sweep is linear:

The complete code

The from-scratch tab is all three techniques — variable window, two-pointer walk, fixed window; the library tab is the O(n²) brute-force version of each, used to verify correctness and as the baseline in the face-off. Flip between them — the brute forces are shorter and obviously correct, and that quadratic obviousness is the trap the linear techniques escape.

"""Two pointers and sliding window — turn many O(n^2) scans into a single O(n) pass by moving two
indices through the data and maintaining a window's state incrementally instead of recomputing it
from scratch. The insight is the same one behind the rolling hash: when a window slides, most of it
is unchanged, so update the little that changed rather than re-examine the whole thing.

Three shapes cover most uses. A VARIABLE-size sliding window grows its right edge and shrinks its
left edge to maintain a property — like the longest substring with no repeated character, where the
right pointer extends the window and the left pointer jumps forward whenever a duplicate appears.
The TWO-POINTER shape walks two indices from opposite ends of a sorted array toward each other — like
finding a pair that sums to a target, moving the pointer that brings the sum closer. A FIXED-size
window slides a constant-width window across the data, adding the entering element and removing the
leaving one in O(1). All three replace a nested loop with a single sweep, and the trick is always to
carry state across the slide instead of rebuilding it.
"""


# region: sliding_window
def longest_unique_substring(s, trace=None):
    """Longest substring with no repeated character, in one pass. `last` remembers each character's
    most recent index. Extend the window's right edge over every character; when the new character
    was already seen INSIDE the current window, jump the left edge just past that previous
    occurrence (shrinking the window to stay duplicate-free). Track the largest window. O(n): each
    index moves forward only, never back. Returns (length, the substring)."""
    last = {}
    left = 0
    best_len, best_l = 0, 0
    for right, ch in enumerate(s):
        if ch in last and last[ch] >= left:
            left = last[ch] + 1                   # contract: skip past the duplicate
        last[ch] = right
        if right - left + 1 > best_len:
            best_len, best_l = right - left + 1, left
        if trace is not None:
            trace.append((left, right, best_len))
    return best_len, s[best_l:best_l + best_len]
# endregion


# region: two_pointer
def two_sum_sorted(nums, target):
    """In a SORTED array, find two values summing to `target`, using two pointers from the ends. If
    the current sum is too small, move the left pointer right (only larger values remain that way);
    if too large, move the right pointer left. Each step discards one candidate, so it's O(n) — no
    nested loop, no hash set. Returns the (i, j) indices, or None."""
    lo, hi = 0, len(nums) - 1
    while lo < hi:
        s = nums[lo] + nums[hi]
        if s == target:
            return (lo, hi)
        if s < target:
            lo += 1                               # need a bigger sum → raise the low end
        else:
            hi -= 1                               # need a smaller sum → lower the high end
    return None
# endregion


# region: fixed_window
def max_window_sum(nums, k):
    """Maximum sum of any k consecutive elements, by sliding a fixed-width window: compute the first
    window's sum, then for each step add the entering element and subtract the leaving one — O(1)
    per slide instead of re-summing k elements. O(n) total. Returns the best sum."""
    if k > len(nums) or k <= 0:
        return None
    window = sum(nums[:k])
    best = window
    for i in range(k, len(nums)):
        window += nums[i] - nums[i - k]           # roll: +entering, -leaving
        best = max(best, window)
    return best
# endregion

"""The contrast: the O(n^2) (or worse) brute-force versions the linear techniques replace. These are
the correctness references AND the baselines the face-off times against. There's no single stdlib
call for these problems — two pointers and sliding window are techniques, not library functions —
so the 'library' here is the naive nested-loop way you'd write without the technique.
"""


# region: brute
def longest_unique_brute(s):
    """Longest substring with no repeat, the obvious way: for every start index, extend until a
    repeat, tracking the best. O(n^2) — it re-scans overlapping regions the sliding window handles
    in one pass. The correctness reference and the baseline."""
    best = 0
    n = len(s)
    for i in range(n):
        seen = set()
        for j in range(i, n):
            if s[j] in seen:
                break
            seen.add(s[j])
        best = max(best, len(seen))
    return best


def two_sum_brute(nums, target):
    """Check every pair — O(n^2). Returns a matching (i, j) with i < j, or None."""
    n = len(nums)
    for i in range(n):
        for j in range(i + 1, n):
            if nums[i] + nums[j] == target:
                return (i, j)
    return None


def max_window_sum_brute(nums, k):
    """Re-sum every window from scratch — O(n·k). The baseline the O(1)-slide beats."""
    if k > len(nums) or k <= 0:
        return None
    best = None
    for i in range(len(nums) - k + 1):
        s = sum(nums[i:i + k])
        best = s if best is None else max(best, s)
    return best
# endregion

Scratch vs library

These techniques teach a way of seeing more than a specific algorithm: when you spot a nested loop that re-examines overlapping ranges, ask whether the inner work can be maintained incrementally as an outer window slides — and if the property is monotone, it usually can, collapsing O(n²) to O(n). That's the same amortized-reuse insight that ran through the rolling hash, KMP's non-rewinding scan, and the dynamic array's appends, now packaged as a reusable pattern for the enormous class of contiguous-range and sorted-pair problems. The face-off's 400-fold gap is what that reuse buys. There's no library call because it's a technique, not a function — which is exactly why it's worth internalizing: the skill is recognizing the sliding-window shape in a problem that doesn't announce itself as one, and knowing the monotonicity precondition that tells you it's safe. Building the three shapes yourself is what trains that recognition.

Where you'll actually meet it

Sliding window and two pointers appear across systems and everyday code. Stream and time-series processing compute moving averages, rate limits, and windowed aggregates with fixed windows (network monitoring, financial tick data, sensor smoothing). Text processing and search use variable windows for substring and n-gram problems. Sorted-data pair and triple search (two-sum, three-sum, closest-pair) uses the two-ends walk. Merge steps in merge sort and merge joins in databases are two-pointer walks over sorted sequences. The partition step of quicksort and the Dutch-national-flag partitioning are two-pointer. Rate limiters and sliding-window counters in distributed systems use the fixed-window idea. Deduplication and run-length problems, and much of competitive programming and technical interviews, lean on these patterns. Anywhere a computation over contiguous ranges or sorted pairs can be maintained incrementally, a two-pointer sweep is likely the efficient answer.

Takeaways

Two-pointer and sliding-window techniques turn O(n²) nested scans into O(n) single passes by moving two indices through the data and maintaining the window's state incrementally — a variable window that grows right and shrinks left to keep an invariant, a two-pointer walk converging from both ends of sorted data, or a fixed window that adds-one-removes-one as it slides. The linear time comes from monotone pointer movement (each index only advances, total ≤ 2n) plus O(1) per-slide updates that reuse the previous window's state — the same amortization behind the rolling hash and KMP. On the longest-unique-substring worst case it did 400× less work than brute force. The precondition is that the window's property be monotone and incrementally maintainable; recognizing that shape is the real skill.

The paradigms tier ends with one more application of an old friend to a new setting. Binary search on the answer (next) applies binary search not to a sorted array but to the space of possible answers to an optimization problem — repeatedly guessing a candidate answer and asking a yes/no feasibility question — turning "find the optimal value" into "check whether a value works," and solving a surprising range of problems that look nothing like search at first glance.