Two Pointers 101

What two pointers is and when to use it

The idea

Two pointers means keeping two indices into the same sequence (or one index into each of two sequences) and moving them according to a rule, so that together they cover all useful pairs in O(n) instead of O(n²). The trick works because of some order in the data: once a pointer moves past a position, you can prove you never need to return to it.

There are three shapes you will see again and again:

1. Opposite ends. left starts at 0, right at the end, and they move towards each other. Used on sorted arrays and palindromes.
2. Same direction, different speeds. A read pointer scans every element and a write pointer marks where the next kept element goes. Used for in-place filtering and removing duplicates.
3. One pointer per sequence. Walk two strings or arrays together, like the merge step of merge sort, or checking whether one string is a subsequence of another.

Signals in a problem statement

• The array is sorted, or sorting it does not break the question.
• "Find a pair or triplet with sum equal to target."
• "Palindrome", "reverse", "compare from both ends".
• "Remove in place", "move zeros", "return the new length".
• "Is s a subsequence of t?"
• "Maximise area or width between two lines."

Why it is correct

For a sorted array with left and right, if a[left] + a[right] is too small, then pairing a[left] with anything left of right is also too small, so a[left] can be discarded. That one-line argument is what interviewers want to hear. Always be ready to say why moving a pointer cannot skip the answer.

Core patterns with templates

1. Pair sum on a sorted array

def pair_sum(a, target):
    lo, hi = 0, len(a) - 1
    while lo < hi:
        s = a[lo] + a[hi]
        if s == target:
            return [lo, hi]
        if s < target:
            lo += 1
        else:
            hi -= 1
    return []

2. Palindrome check that skips non-letters

def is_palindrome(s):
    lo, hi = 0, len(s) - 1
    while lo < hi:
        if not s[lo].isalnum():
            lo += 1
        elif not s[hi].isalnum():
            hi -= 1
        elif s[lo].lower() != s[hi].lower():
            return False
        else:
            lo += 1
            hi -= 1
    return True

3. Read and write pointers

def remove_duplicates_sorted(a):
    w = 0
    for r in range(len(a)):
        if r == 0 or a[r] != a[r - 1]:
            a[w] = a[r]
            w += 1
    return w

4. Subsequence check

def is_subsequence(s, t):
    i = 0
    for ch in t:
        if i < len(s) and s[i] == ch:
            i += 1
    return i == len(s)

5. Three numbers summing to zero

Sort, fix the first element, then run pattern 1 on the rest. Skip equal neighbours to avoid duplicate triplets.

def three_sum(a):
    a.sort()
    out = []
    for i in range(len(a) - 2):
        if i and a[i] == a[i - 1]:
            continue
        lo, hi = i + 1, len(a) - 1
        while lo < hi:
            s = a[i] + a[lo] + a[hi]
            if s < 0:
                lo += 1
            elif s > 0:
                hi -= 1
            else:
                out.append([a[i], a[lo], a[hi]])
                lo += 1
                while lo < hi and a[lo] == a[lo - 1]:
                    lo += 1
                hi -= 1
    return out

Example: [-1,0,1,2,-1,-4] sorts to [-4,-1,-1,0,1,2] and yields [-1,-1,2] and [-1,0,1].

Complexity, mistakes and edge cases

Complexity

Common mistakes

• Using <= instead of < in the loop condition, which lets one element pair with itself.
• Forgetting to move a pointer in some branch, which causes an infinite loop. Every iteration must move at least one pointer.
• Duplicate results in 3-sum style questions. Skip equal values both for the fixed element and after a match.
• Sorting when indices matter. If the answer must be original indices, sorting loses them; sort (value, index) pairs or use a hash map instead.
• Character classes. Python's isalnum() accepts digits and Unicode letters; confirm with the interviewer what counts.

Edge cases

Empty array, one element, all elements equal, no valid pair, many valid pairs, negative numbers, and integer overflow in languages other than Python (mention it if you are coding in Java or C++).

The greedy argument for "container with most water"

With two lines at lo and hi, the area is min(h[lo], h[hi]) * (hi - lo). Moving the taller line inward can only shrink the width and cannot raise the minimum, so it never helps. Therefore always move the shorter line. Being able to state this argument is often worth as much as the code itself, because it shows you understand why the pointer moves are safe.

Variations and practise

How interviewers twist it

• Closest sum instead of exact. Track the best difference seen while running the same pointer moves.
• Count pairs instead of finding one. When a[lo] + a[hi] < target, every index between lo and hi also pairs with lo, so add hi - lo at once.
• k-sum. Generalise 3-sum by recursion: fix one element, solve (k-1)-sum on the rest, until you reach the two-pointer base case. Time is O(n^(k-1)).
• Unsorted input with "O(1) space". Sorting in place is often acceptable; ask.
• Linked lists. Fast and slow pointers find the middle of a list, detect a cycle, or locate the n-th node from the end. You will meet these in the Linked List card.
• Strings with a backspace character. Walk both strings from the end, skipping characters that are erased, and compare as you go.

Two pointers versus sliding window

Both use two indices. In sliding window the two pointers define a contiguous range whose contents you track (a sum, a count). In classic two pointers you usually care about the two elements at the pointers. Knowing which one you are using helps you explain your approach.

Practise

The problems below start with palindromes and subsequence checks, move to pair sums on sorted input, and finish with the greedy area argument and triplets. For each one, say out loud why moving a pointer cannot skip the answer before you code it.