Patterns

Two pointers

Two pointers means you keep two indexes into a sequence and move them according to a rule, instead of checking every pair. The rule is the whole algorithm. "I will use two pointers" is not yet a plan until you can say which pointer moves, and why moving it cannot skip the answer.

There are two shapes you will actually use. Inward pointers start at the ends of a sorted sequence and walk toward each other. Same-direction pointers both start at the left, and one of them may run ahead. Sliding windows are a special case of the second shape, covered on the sliding window page. This page stays with pair-finding and compacting.

Inward pointers on a sorted sequence

If the sequence is sorted, a pair that sums to too little can only be fixed by raising the left value. A pair that sums to too much can only be fixed by lowering the right value. That is the justification for moving one side. Without the sort, the justification disappears, and you should use the index map from the arrays and hashing page instead.

Original task: donation amounts are sorted ascending. Return the two amounts that add up to a campaign goal, or None. Amounts may be reused only if they appear twice. Do not use an amount index twice.

def campaign_pair(amounts: list[int], goal: int) -> tuple[int, int] | None:
    left, right = 0, len(amounts) - 1
    while left < right:
        total = amounts[left] + amounts[right]
        if total == goal:
            return amounts[left], amounts[right]
        if total < goal:
            left += 1
        else:
            right -= 1
    return None


assert campaign_pair([1, 4, 6, 8, 9], 10) == (1, 9)
assert campaign_pair([2, 2, 3], 4) == (2, 2)
assert campaign_pair([1, 2, 3], 10) is None

Each step moves one pointer, and the pointers together cross the array once, so the scan is linear. If the caller did not sort the input, sorting first adds an n log n term, and that term dominates. Quote both versions. Extra space is constant if you are allowed to sort in place, and linear if you sort a copy because the caller needs the original order.

The loop condition is left < right, not left <= right. When the indexes meet, you would be pairing an amount with itself. The second assert still works because the two 2s are different indexes. An empty list and a one-element list never enter a successful pair, and the function returns None. Try those before you trust a variant that returns indexes instead of values.

Why the move is safe: suppose amounts[left] + amounts[right] is less than the goal. Every sum that uses this left value and a smaller right value is even smaller, because the array is sorted. So this left value has no partner to its left of right. Moving left up is the only remaining place that partner could be. The symmetric argument applies when the sum is too large. If you cannot tell that story, you are not ready to code the loop. You would be moving indexes because a diagram told you to.

Same-direction pointers

Same-direction pointers are how you compact a sequence or copy the part you want to keep, in one pass, often in place. One index reads. The other writes. They are not searching for a numeric target. They are filtering.

Original task: a log of sensor readings should drop adjacent duplicates. Return the number of readings kept, and write the kept readings into the front of the same list. The caller will ignore everything after that count. This is the usual "in place" contract: you may use the input as the output buffer.

def compact_adjacent(readings: list[int]) -> int:
    if not readings:
        return 0
    write = 1
    for read in range(1, len(readings)):
        if readings[read] != readings[write - 1]:
            readings[write] = readings[read]
            write += 1
    return write


data = [1, 1, 2, 2, 2, 3]
assert compact_adjacent(data) == 3
assert data[:3] == [1, 2, 3]
assert compact_adjacent([]) == 0

The read index visits every element once. The write index only moves when a new value is kept. Time is linear. Extra space is constant. The empty list is the edge that forces the early return. A list of one element never enters the loop and correctly returns 1. A list of all duplicates returns 1 and leaves the first value in place.

The comparison is against readings[write - 1], the last kept value, not against readings[read - 1]. Those differ once you have skipped anything. If every duplicate is only adjacent, comparing with the previous input element happens to work. The moment the task changes to "drop any value already kept," you need a set, and you have left the two-pointer pattern. Say that switch out loud so you do not force pointers onto a problem that needs memory.

Choosing between the patterns

Ask three questions. Is the data ordered in the way my move assumes? If not, can I sort it without breaking the required output, such as original indexes? Do I need extra memory to be small? Inward pointers want sorted order. Same-direction pointers want a single forward pass with a simple keep-or-skip rule. A hash map wants neither, and pays with memory. Binary search is a third option when you are hunting one boundary inside a sorted range rather than a pair.

A practical interview sequence: state the brute force pair loop and its n-squared cost, state the pointer method and its cost, then code the pointer method if the data is sorted or you are allowed to sort. Interviewers who wanted the map instead will usually say so if you have made the trade explicit. Interviewers who wanted pointers will be unhappy if you sort an array and then still use a map without noticing.

Pitfalls

Moving both pointers after a match is sometimes required and sometimes fatal. If the task is "any one pair," you return. If the task is "count every pair of a target sum," you must decide how to handle duplicates so you do not double-count, and you usually advance the side you just used, skipping repeated values in a controlled way. Do not copy the return-immediately loop and then bolt a counter onto it.

Another pitfall is sorting when the answer must preserve the original indexes. Sort pairs of (value, index) or do not sort. A third pitfall is using inward pointers on a nearly sorted array that is only "almost" ordered. Almost sorted is not sorted. One inversion makes the "raising the left side must help" story false.

On strings, the same shapes show up as a left and right index walking toward a middle to check a palindrome, which the strings page does with its own example. The justification there is symmetry, not a numeric sum. The code looks similar. The reason is different. Be able to say the reason.

Practice drill

Implement campaign_pair so it returns indexes instead of values, and add a case where the correct indexes are not the first match a tired reader would guess. Then implement a same-direction filter that keeps only positive readings, still in place, and state the complexity. Finally, take a pair-sum task on unsorted data and write both the map solution and the sort-then-pointers solution. Time both on a list of a hundred thousand random integers if you want evidence, not folklore, about the constants. The linear map often wins despite the worse-looking memory, because the sort's n log n is real. Knowing that keeps you from treating pointers as morally superior.