Sliding Window and Two Pointers

TL;DR: When a problem asks about a contiguous subarray or substring, reach for a sliding window: expand the right edge to include elements, shrink the left edge when a constraint breaks, and keep a running answer so each element is touched at most twice. When the data is sorted (or you want pairs from both ends), two pointers collapse the same O(n^2) scan into O(n).

When each one fires

The trigger words are concrete. "Contiguous subarray", "substring", "window of size k", "longest/shortest range satisfying X" mean sliding window. "Sorted array", "pair that sums to target", "move inward from both ends", or "fast and slow pointer" mean two pointers. The shared idea is that you never restart the scan: state computed for one position is reused for the next, so the work is linear instead of quadratic.

The mistake that reveals a weak candidate is recomputing the window from scratch on every step. That is the O(n*k) trap. The whole point is to add the entering element and subtract the leaving one in O(1).

The spine above is the window loop itself, with the constant-time update and the left edge that never moves backward marked as the two things the screen is actually testing.

Sliding window: longest substring without repeats

def longest_unique(s: str) -> int:
    last = {}           # char -> most recent index
    start = 0           # left edge of the window
    best = 0
    for i, ch in enumerate(s):
        # if ch was seen inside the current window, jump start past it
        if ch in last and last[ch] >= start:
            start = last[ch] + 1
        last[ch] = i
        best = max(best, i - start + 1)
    return best

assert longest_unique("abcabcbb") == 3   # "abc"
assert longest_unique("bbbbb") == 1
assert longest_unique("") == 0

The left edge only ever moves right, so each character is visited a constant number of times: O(n) time, O(k) space for the alphabet. The bug interviewers watch for is last[ch] >= start. Without that guard, a repeat that lives outside the current window wrongly drags start backward.

Trace "abba" to see the guard earn its place. At index 0, a: the window is [0, 0], best 1. Index 1, b: [0, 1], best 2. Index 2, b again: b was last seen at 1, inside the window, so start jumps to 2 and the window is [2, 2]. Index 3, a: a was last seen at 0, which is before start, so the guard leaves start at 2, the window is [2, 3], and best stays 2. Without the guard, start would jump to 1 and the window [1, 3] would be reported as three unique characters when it contains b twice.

Two pointers: pair sum in a sorted array

def has_pair_sum(nums: list[int], target: int) -> bool:
    lo, hi = 0, len(nums) - 1     # nums is sorted ascending
    while lo < hi:
        cur = nums[lo] + nums[hi]
        if cur == target:
            return True
        if cur < target:
            lo += 1               # need a larger sum
        else:
            hi -= 1               # need a smaller sum
    return False

assert has_pair_sum([1, 2, 4, 7, 11, 15], 13) is True   # 2 + 11
assert has_pair_sum([1, 2, 4, 7], 100) is False

Each step discards exactly one candidate, so the whole array is swept once: O(n) after the sort. The reason a step can safely discard is the sort. If the sum is below the target, the low element cannot pair with anything, because the high element is the largest partner still available and even that was not enough, so the low element is finished. The mirror argument retires the high element when the sum is too large. The fast/slow variant of two pointers (one moves one step, the other two) is how you detect a cycle in a linked list or find a midpoint in a single pass.

Common pitfalls

• Recomputing instead of sliding. Summing the window every step is O(n*k). Maintain the running value incrementally.
• Off-by-one on the window size. The length of an inclusive window is right - left + 1, not right - left.
• Forgetting the in-window check. For "no repeats" style problems, an index seen long ago must not move the left edge.
• Two pointers on unsorted data. The technique assumes order. If the input is not sorted and you cannot sort it, a hash set or sliding window is usually the real answer.

Key takeaways

• Contiguous-range questions are sliding-window questions: grow right, shrink left, keep a running answer, touch each element O(1) times.
• Sorted-array or pair-from-both-ends questions are two-pointer questions: each step eliminates one candidate for an O(n) sweep.
• The signal of competence is incremental update (add the entering element, remove the leaving one), never recomputing the window.
• State the complexity out loud: most of these go from O(n^2) brute force to O(n) time and O(1) or O(k) space.