Two Pointers

Two pointers is the first pattern to master — it is simple, it appears constantly, and it turns many O(n²) brute forces into clean O(n) solutions.

The idea

On a sorted array, you don’t need the O(n²) brute force of checking every pair. Put one pointer at the left and one at the right. Look at the two values:

• If their sum is too small, the only way to increase it is to move the left pointer rightward (to a bigger value).
• If too big, move the right pointer leftward (to a smaller value).
• If it’s exactly the target, you’re done.

Each step removes one position from consideration, so you traverse the whole array once: O(n) time, O(1) space.

The template

def two_sum_sorted(a, target):
    i, j = 0, len(a) - 1
    while i < j:
        s = a[i] + a[j]
        if s == target:
            return [i, j]
        if s < target:
            i += 1          # need a bigger sum → move left pointer up
        else:
            j -= 1          # need a smaller sum → move right pointer down
    return []
# two_sum_sorted([1,3,4,5,7,11], 9) -> [2, 3]   (4 + 5)

Worked example: valid palindrome

Two pointers also works from both ends toward the middle — comparing as they go:

def is_palindrome(s):
    s = [c.lower() for c in s if c.isalnum()]
    i, j = 0, len(s) - 1
    while i < j:
        if s[i] != s[j]:
            return False
        i += 1; j -= 1
    return True
# is_palindrome("A man, a plan, a canal: Panama") -> True

Worked example: 3Sum

Many “find a triplet” problems are “fix one element, then two-pointer the rest.” Sort first, fix nums[i], and two-pointer the remaining subarray for the complement -nums[i]:

def three_sum(nums):
    nums.sort()
    res = []
    for i in range(len(nums) - 2):
        if i > 0 and nums[i] == nums[i-1]:        # skip duplicates
            continue
        l, r = i + 1, len(nums) - 1
        while l < r:
            s = nums[i] + nums[l] + nums[r]
            if s == 0:
                res.append([nums[i], nums[l], nums[r]])
                while l < r and nums[l] == nums[l+1]: l += 1   # skip dup
                while l < r and nums[r] == nums[r-1]: r -= 1
                l += 1; r -= 1
            elif s < 0: l += 1
            else:       r -= 1
    return res
# three_sum([-1,0,1,2,-1,-4]) -> [[-1,-1,2],[-1,0,1]]

3Sum is O(n²): an outer loop (n) with a two-pointer inner pass (n). Sorting is O(n log n), dominated by the n².

Step-by-step walkthrough

Trace Container With Most Water on height = [1, 8, 6, 2, 5, 4, 8, 3, 7]. The two pointers start at the ends; each step computes the area and moves the shorter wall inward, because moving the taller one can never produce a bigger area.

The pointers meet after 8 steps — one pass, O(n) — and the answer is 49 (found when left=1, right=8). A brute-force double loop would have checked all 36 pairs.

When to reach for it

Signals that two pointers fits: the array is sorted (or you can sort it), and you need to find a pair/triplet, reverse or rearrange in place, or compare from both ends. It is also the “in-place” workhorse: removing duplicates from a sorted array, moving zeros, partitioning.

Pitfalls

• Forgetting the array must be sorted for the sum-based version. If it isn’t sorted and you can’t sort it, use a hash map instead (Lesson 6).
• Infinite loops / off-by-one. Always advance at least one pointer each iteration, and use while i < j (not <=) for pair problems.
• Duplicate handling in 3Sum. Skip equal neighbours or you’ll emit duplicate triplets — a classic bug.

Recap

On a sorted array, two pointers converging from the ends solves pair/triplet problems in O(n) (or O(n²) for 3Sum) instead of O(n²)/O(n³): move the left pointer up when the sum is too small, the right down when too big. It also handles two-ends comparison (palindrome) and in-place rearrangement. Signal: sorted + find a pair / in place.

Practice: 12 solved problems on two pointers → — cover each one, solve it yourself, then check the tested code.

Next: Lesson 4 — Sliding Window, two pointers’ close cousin for contiguous sub-arrays.