Two Pointers & Sliding Window

The idea

Many array and string questions ask about pairs or contiguous ranges: “two numbers with sum x”, “the best k consecutive values”, “the longest stretch with some property”. Trying every pair or range costs O(n²) or more.

Both techniques here use two indices that only move forward. Because neither ever goes back, the total work is O(n).

Two pointers: a pair with a given sum

The array must be sorted. Start with lo at the first element and hi at the last:

• sum too small → move lo right (a bigger number),
• sum too big → move hi left (a smaller number),
• equal → found.

For [1, 3, 4, 6, 8, 11, 13, 15] and target 19:

Why is skipping safe? When the sum is too small, a[lo] plus the largest remaining number is still not enough, so a[lo] cannot be in any pair. Likewise a too-large sum rules out a[hi]. Every step eliminates one number, so at most n − 1 steps are needed. For target 30, the pointers meet after 7 steps: no pair exists. Checking all pairs would take 28 additions.

Fixed sliding window: the largest sum of k in a row

window ← a[0] + … + a[k − 1]
for i from k to n − 1:
    window ← window + a[i] − a[i − k]        # one in, one out
    best ← max(best, window)

For [2, 1, 5, 1, 3, 2, 6, 1, 4] with k = 3 the window sums are 8, 7, 9, 6, 11, 9, 11: the best is 11 ([3, 2, 6], positions 4 to 6). Each slide costs 2 operations instead of k.

Variable sliding window: longest substring without repeats

Keep a window [lo, hi] whose characters are all different. Move hi forward one character at a time. If the new character already appears in the window, jump lo just past its previous position. Remember where each character was last seen in a hash map.

The answer for “abcabcbb” is “abc” (length 3); for “pwwkew” it is “wke”.

Recognising the pattern

• “pair” or “triplet” in a sorted array → two pointers from both ends (3-sum = fix one, two pointers on the rest).
• “contiguous” subarray or substring of fixed length → fixed window.
• “longest / shortest contiguous … such that …” where the condition only gets worse as the window grows → variable window.
• Negative numbers can break the “shrink when too big” rule for sums; then use prefix sums with a hash map instead.

Code

import random
from itertools import combinations

def pair_with_sum(a, target):
    """Two pointers on a SORTED array: O(n) instead of checking all pairs."""
    lo, hi, steps = 0, len(a) - 1, 0
    while lo < hi:
        steps += 1
        s = a[lo] + a[hi]
        if s == target:
            return (lo, hi), steps
        if s < target:
            lo += 1                     # need a bigger sum: move the left pointer right
        else:
            hi -= 1                     # need a smaller sum: move the right pointer left
    return None, steps

def max_window_sum(a, k):
    """Fixed-size sliding window: add the element that enters, subtract the one that leaves."""
    window = sum(a[:k])
    best, start = window, 0
    for i in range(k, len(a)):
        window += a[i] - a[i - k]
        if window > best:
            best, start = window, i - k + 1
    return best, start

def longest_unique(s):
    """Variable-size window: grow on the right, shrink on the left when a character repeats."""
    last, lo, best = {}, 0, (0, 0)
    for hi, ch in enumerate(s):
        if ch in last and last[ch] >= lo:
            lo = last[ch] + 1           # jump past the previous copy of ch
        last[ch] = hi
        if hi - lo + 1 > best[1] - best[0]:
            best = (lo, hi + 1)
    return s[best[0]:best[1]]

A = [1, 3, 4, 6, 8, 11, 13, 15]
print(pair_with_sum(A, 19))
# ((2, 7), 3)
print(pair_with_sum(A, 7))
# ((0, 3), 5)
print(pair_with_sum(A, 30))
# (None, 7)
B = [2, 1, 5, 1, 3, 2, 6, 1, 4]
print(max_window_sum(B, 3))
# (11, 4)
print(longest_unique('abcabcbb'), longest_unique('pwwkew'), longest_unique('dvdfaxdq'))
# abc wke vdfax

rng = random.Random(6)                  # compare with brute force
for _ in range(2000):
    a = sorted(rng.sample(range(1, 60), rng.randint(2, 12)))
    t = rng.randint(2, 110)
    found = pair_with_sum(a, t)[0]
    assert (found is not None) == any(x + y == t for x, y in combinations(a, 2))
    b = [rng.randint(-5, 9) for _ in range(rng.randint(1, 12))]
    k = rng.randint(1, len(b))
    assert max_window_sum(b, k)[0] == max(sum(b[i:i + k]) for i in range(len(b) - k + 1))
    s = ''.join(rng.choice('abcd') for _ in range(rng.randint(1, 12)))
    assert len(longest_unique(s)) == max(j - i for i in range(len(s)) for j in range(i + 1, len(s) + 1) if len(set(s[i:j])) == j - i)
print('all three match brute force')
# all three match brute force

Common mistakes

• Using opposite-end pointers on an unsorted array. The “too small, move left pointer” rule needs sorted data.
• Re-adding the whole window at every step. Then the “sliding” window is O(n·k) again.
• Moving lo backwards in the variable window. The check last[ch] >= lo stops an old, already-skipped copy from pulling lo back.
• Off-by-one window sizes. The window [lo, hi] has hi − lo + 1 elements.
• Applying the shrink rule to sums with negative numbers. Growing the window can then make the sum smaller, so the greedy shrink is no longer correct.