Two Pointers Pattern: Template + 201 LeetCode Problems

What the two pointers pattern is

Two pointers walk the input with two indices whose movement is driven by a comparison rather than by a loop counter, and the whole technique rests on one idea: if the input is ordered, the comparison tells you which pointer cannot possibly be part of the answer, so moving it throws away a whole family of candidates at once. In the converging form the pointers start at opposite ends and step inward — for a target sum, a total that is too small can only be fixed by a larger left value, so the left pointer moves and every pair involving the old left value is eliminated in one step. The same-direction form uses a slow write index behind a fast read index and is how in-place filtering and de-duplication are done without extra memory. The fast-and-slow variant advances one pointer twice as fast as the other, which detects a cycle in a linked list and finds its midpoint without knowing the length.

When to use it

• —The input is sorted, or sorting it first does not destroy the answer.
• —You are looking for a pair, triple, or a partition point rather than a subarray.
• —The problem asks for an in-place rewrite in O(1) extra space.
• —A linked list needs a midpoint, a cycle check, or the nth node from the end in one pass.

The two pointers template in Python

The shape, not a solution to any one problem. Adapt the condition and the summary being maintained; the skeleton stays the same across the 201 problems listed below.

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

    while left < right:
        total = nums[left] + nums[right]
        if total == target:
            return [left, right]
        if total < target:
            left += 1      # only a larger left value can reach the target
        else:
            right -= 1     # only a smaller right value can
    return []

Complexity characteristics

Time

O(n), or O(n log n) when the input has to be sorted first

Auxiliary space

O(1)

Each pointer only ever moves in one direction, so between them they take at most n steps and the scan is linear. When the input arrives unsorted the sort dominates and the whole solution is O(n log n) — worth saying out loud, because it is exactly the difference between this and a hash-map solution that stays linear. The extra space is two integers, and the fast-and-slow variant on a linked list is likewise O(1), which is normally the constraint being tested.

All 201 two pointers LeetCode problems

Every problem in the library the two pointers pattern applies to, grouped by LeetCode's own difficulty rating. 169 of the 201 carry a complete Python solution with a worked example and complexity analysis; the rest are listed for completeness, with the LeetCode Premium ones marked.

Related patterns

Problems sit in more than one pattern more often than not, and the overlap is where the interesting follow-up questions live.

Two Pointers pattern FAQ

More ways in: all 22 patterns, the curated study lists, or the full problem list.