Two Pointers & Sliding Window

The two-pointer technique#

Two pointers means walking through data with two indices at once — instead of one index and a nested loop — so that a problem which looks like it needs to compare every pair can often be solved in a single coordinated pass.

Two sum on a sorted array#

Given a sorted array, find two numbers that add up to a target value. (The hash tables page solved this same "two sum" idea for an unsorted array using a hash map — this is the sorted-array version, and it takes advantage of that sortedness directly, no extra memory required.)

def two_sum_sorted(arr, target):
    left, right = 0, len(arr) - 1

    while left < right:
        current_sum = arr[left] + arr[right]
        if current_sum == target:
            return [left, right]
        elif current_sum < target:
            left += 1          # sum too small: move the left pointer up to increase it
        else:
            right -= 1         # sum too large: move the right pointer down to decrease it

    return None

print(two_sum_sorted([1, 3, 4, 6, 8, 11], 10))   # [2, 3]  ->  4 + 6 == 10

Tracing it: left=0, right=5 → 1 + 11 = 12, too big → right=4. left=0, right=4 → 1 + 8 = 9, too small → left=1. left=1, right=4 → 3 + 8 = 11, too big → right=3. left=1, right=3 → 3 + 6 = 9, too small → left=2. left=2, right=3 → 4 + 6 = 10 — match, return [2, 3].

Why this works: because the array is sorted, moving left up can only ever increase the sum, and moving right down can only ever decrease it — so at every step, there's exactly one correct direction to move, and the two pointers provably converge without ever needing to revisit a pair. This runs in O(n) time with O(1) extra space — even better than the hash-map version's O(n) space, precisely because sortedness gives you this converging-pointer structure for free. The trade-off mirrors binary search's: this technique requires sorted input, and sorting first (if it isn't already) costs O(n log n).

Reverse an array in place#

Another classic two-pointer pattern: start one pointer at each end and swap inward.

def reverse_in_place(arr):
    left, right = 0, len(arr) - 1

    while left < right:
        arr[left], arr[right] = arr[right], arr[left]
        left += 1
        right -= 1

    return arr

print(reverse_in_place([1, 2, 3, 4, 5]))   # [5, 4, 3, 2, 1]

This runs in O(n) time (roughly n/2 swaps) and O(1) space — no second array is ever allocated, unlike building a reversed copy with arr[::-1], which costs O(n) extra space to hold the copy.

The sliding window technique#

Sliding window is the two-pointer idea applied specifically to problems about contiguous subarrays or substrings. The naive approach to "find the best window of data" recomputes something (a sum, a count, a set of characters) from scratch for every possible window — wasteful, since neighboring windows share almost all of their content. A sliding window instead maintains a running window and incrementally updates it — adding one new element and removing one old element as the window slides — reusing prior work instead of throwing it away every time.

Maximum sum subarray of size k#

def max_sum_subarray(arr, k):
    window_sum = sum(arr[:k])          # sum of the first window, computed once
    max_sum = window_sum

    for i in range(k, len(arr)):
        window_sum += arr[i] - arr[i - k]   # slide: add the new element, drop the oldest one
        max_sum = max(max_sum, window_sum)

    return max_sum

print(max_sum_subarray([2, 1, 5, 1, 3, 2], 3))   # 9  ->  the window [5, 1, 3]

Tracing it on [2, 1, 5, 1, 3, 2], k=3: the first window is [2, 1, 5], sum 8. i=3: add arr[3]=1, drop arr[0]=2 → 8 + 1 - 2 = 7. i=4: add arr[4]=3, drop arr[1]=1 → 7 + 3 - 1 = 9 → new max 9. i=5: add arr[5]=2, drop arr[2]=5 → 9 + 2 - 5 = 6. Final answer: 9, from the window [5, 1, 3] (indices 2–4).

This runs in O(n) — every element is added to the running sum exactly once and removed exactly once — versus the brute-force approach of summing every window from scratch, which costs O(n·k).

Longest substring without repeating characters#

This variant uses a variable-size window instead of a fixed size k: grow the window by moving the right edge forward, and whenever a repeated character shows up, shrink from the left edge until the repeat is resolved.

def longest_unique_substring(s):
    seen = {}              # character -> most recent index it was seen at
    left = 0
    longest = 0

    for right, char in enumerate(s):
        if char in seen and seen[char] >= left:
            left = seen[char] + 1     # shrink the window past the earlier occurrence
        seen[char] = right
        longest = max(longest, right - left + 1)

    return longest

print(longest_unique_substring("abcabcbb"))   # 3  ->  "abc"

Tracing it on "abcabcbb": a, b, c are each new, so the window grows to "abc" (length 3). At right=3 (a), a was last seen at index 0, which is >= left (0), so left jumps to 1; window is now "bca" (still length 3). At right=4 (b), b was seen at 1, >= left (1), so left jumps to 2; window "cab" (length 3). The pattern continues, and longest never exceeds 3 for the rest of the string — matching the known answer, "abc".

This runs in O(n): the right pointer visits every character exactly once, and the left pointer only ever moves forward, never backward, so across the entire run it also advances at most n times total. Compare that to a brute-force check of every possible substring, which costs O(n²) or worse.

Why these techniques turn O(n²) into O(n)#

Brute force for "does some pair sum to a target" or "what's the best window" typically checks every pair or every window completely independently, from scratch — nested loops, O(n²) or worse. Two pointers and sliding window both exploit the same underlying idea: moving one step rarely requires fully recomputing everything. Two pointers narrow the search space in one direction without ever revisiting old ground; sliding window reuses the previous window's already-computed state, adjusting only for what changed at the edges. Both are, in a sense, disciplined ways of refusing to ask the same question about the same data twice — the exact same principle that made the hash-table approach to two sum beat its nested-loop counterpart.

Common mistakes#

• Using two pointers on unsorted data when the technique's correctness depends on sortedness (as in the two-sum example above) — always confirm the input actually meets that assumption first.
• Forgetting to shrink the sliding window when its condition is violated — for instance, not updating left when a duplicate character shows up — which silently produces a wrong (too-large) answer rather than crashing.
• Recomputing the window's sum or state from scratch on every iteration instead of incrementally updating it — this defeats the entire point of the technique and quietly degrades it back to O(n·k) or worse.
• Off-by-one errors in window size, particularly forgetting that a window spanning indices left to right inclusive has length right - left + 1, not right - left.