Pattern 2 of 27

Two Pointers

Walk two indices toward each other over sorted data so each comparison rules out a whole group of candidate pairs.

Cost: O(n) per inward pass, plus O(n log n) if you sort first
Problems: 6

When to reach for it

The input is sorted, or sorting it does not lose what the question asks for.
You are looking for a pair or triple that hits a target sum.
The prompt asks for the work to happen in place with O(1) extra space.

How it works

On a sorted array, the sum of the smallest and largest remaining element tells you which pointer to move. If the sum is too small, no pair using the current left element can reach the target with any smaller right element, so left moves up. If it is too big, right moves down. Each step discards a whole row or column of the n² pair table, so one pass is enough. 3Sum and 4Sum fix one or two outer elements and run the same inward walk on what is left.

The template

Written for Two Sum II - Input Array Is Sorted (write-up)

def two_sum_sorted(nums, target):
    lo, hi = 0, len(nums) - 1
    while lo < hi:
        total = nums[lo] + nums[hi]
        if total == target:
            return [lo + 1, hi + 1]
        if total < target:
            lo += 1                   # need a bigger sum
        else:
            hi -= 1                   # need a smaller sum
    return []

Open in the editor Trace it line by line

Six problems, in learning order

1.Container With Most WaterLeetCode 11Move the shorter wall, since it is the one limiting the area.Medium
2.3SumLeetCode 15Fix one number, run the inward walk on the rest, and skip repeats at every level.Medium
3.3Sum ClosestLeetCode 16The 3Sum walk, tracking the closest sum instead of an exact hit.Not in the curated 370 yet.Medium
4.4SumLeetCode 18Two fixed outer loops around the inward walk; other languages need overflow care.Medium
5.Trapping Rain WaterLeetCode 42Water above a bar is capped by the smaller of the tallest walls on its left and right.Hard
6.Two Sum II - Input Array Is SortedLeetCode 167The canonical inward walk on a sorted array.Medium

What usually goes wrong

Forgetting to skip duplicate values, which returns the same triplet several times.
Sorting when the question wants the original indices, without keeping them.
Stopping at the first match when more pairs can still exist between the pointers.

Two Pointers, answered

When should I use the two pointers pattern?

The input is sorted, or sorting it does not lose what the question asks for. You are looking for a pair or triple that hits a target sum. The prompt asks for the work to happen in place with O(1) extra space.

What is the time complexity of two pointers?

O(n) per inward pass, plus O(n log n) if you sort first. 3Sum and 4Sum fix one or two outer elements and run the same inward walk on what is left.

Which problem should I start with for two pointers?

Start with Container With Most Water (LeetCode 11, Medium). Move the shorter wall, since it is the one limiting the area. The six problems on this page are in learning order.