Two Pointers

The intuition: two people at a bookshelf

Picture a long shelf of books arranged by thickness: the thinnest on the left, the thickest on the right. You need two books that together are exactly 10 cm thick. You could try every pair, but that takes forever. A better plan: two of you stand at opposite ends of the shelf. One picks up the thinnest book, the other the thickest.

• If together they're too thick, the person on the right swaps their book for the neighbor, a thinner one.
• If they're too thin, the person on the left grabs a thicker book.
• If they're exactly right, you've found your pair.

You walk toward each other and never step back. That's the whole idea behind the two pointers technique: instead of a nested O(n²) loop, you move two indices through the array and get O(n) in a single pass.

Two kinds of two pointers

Kind	How they move	Where you'll see it
From both ends	left from the start, right from the end, toward each other	pair with a given sum in a sorted array, palindrome check, reversing an array
Same direction (fast and slow)	both go left to right, fast ahead, slow behind	in-place filtering, removing duplicates, cycle detection in a linked list

A palindrome check is the most natural example: compare s[left] and s[right], and if the characters match, move both pointers toward the center. The first mismatch means the string isn't a palindrome. If the pointers meet without a mismatch, it is one.

Fast and slow is easiest to think of as reading and writing. fast reads every element, and slow marks where the next "good" one should be written. Say you need to keep only the even numbers: fast walks through everything, every even element is copied to position slow, and then slow moves forward by one.

Step by step: a pair that sums to 10

Take a sorted array and target = 10.

(At step 4 we had 3 + 6 = 9 < 10, so left moved to 4.)

Why it's safe to throw an element away

This is the key point, and it's worth understanding rather than memorizing.

• If nums[left] + nums[right] > target, then the right element overshoots even when paired with the smallest remaining number. With any other number it would be even bigger, so nums[right] can't be part of any valid pair, and you can drop it.
• Symmetrically, if the sum is less than target, then nums[left] falls short even with the largest remaining number, so it's useless too.

Every step eliminates one element that definitely isn't needed, and the correct answer is never lost along the way.

Code template

def pair_sum(nums, target):
    left, right = 0, len(nums) - 1
    while left < right:                 # pointers haven't met yet
        s = nums[left] + nums[right]
        if s == target:
            return [left, right]        # found the pair
        if s < target:
            left += 1                   # too small, take a bigger number
        else:
            right -= 1                  # too big, take a smaller number
    return []                           # no pair

Complexity: why O(n)

• Time O(n). At the start there are n − 1 positions between the pointers. On every iteration exactly one pointer takes a step inward, and the distance shrinks by 1. So there are at most n − 1 iterations. The pointers never move backward, so each element is looked at no more than once.
• Space O(1). All you need is two indices and a sum.

For comparison: checking all pairs costs O(n²), and a hash table gives O(n) time but needs O(n) extra space. On a sorted array, two pointers beat both.

When to think of two pointers in an interview

Signals in the problem statement:

• the array is sorted (or can be sorted in O(n log n)), and you're looking for a pair or triplet with a given sum;
• you need to do something in place, "without extra memory": remove, shift, filter;
• a symmetry check: palindrome, reversal;
• in a linked list you need the middle or a cycle. That's where the fast and slow variant shines.

How to say it out loud: "The array is sorted, so I'll put pointers at both ends. If the sum is greater than the target, the right element can't be in the answer, so I move right. If it's smaller, I move left. Each step discards one element, which gives O(n) time and O(1) space." Interviewers value the explanation of why you can discard an element more than the code itself.

Common mistakes

• left <= right instead of left < right. Then an element can be added to itself. For a pair of distinct elements, the condition has to be strict.
• Using the technique on an unsorted array. Without sorting, the "bigger or smaller" logic stops working. Sort first, or use a hash table.
• Sorting when you need the original indices. Sorting shuffles the indices, so store (value, original index) pairs.
• Moving both pointers at once for no reason. On each step, move the pointer whose element is guaranteed to be useless.
• Sum overflow in Java, C++, and Go with large numbers. If values are close to the int limit, compute the sum as a long.

Now you understand not just how the technique works, but why it's correct. Next in this chapter you'll find problems that show it off in different variations.