Two-Pointer Technique

Concepts covered: Two-Pointer

A two-pointer solution keeps 2 indexes into one sequence and moves them based on the values they point at. Neither pointer ever reverses direction. Starting from opposite ends, left only rises while right only falls. Each step shrinks the gap between them by at least 1, so on a list of n items the loop ends within n - 1 steps. The skill lies in proving that each move discards only values that can't be part of the answer.

Pointers that meet in the middle

A palindrome reads the same in both directions: character 0 must equal the last character, character 1 must equal the second to last, and so on inward. Put left at the start and right at the end, compare the 2 characters, then step both pointers toward the middle. The first mismatch ends the check, and if the pointers meet without one, every mirrored pair matched.

def is_palindrome(s):
    left = 0
    right = len(s) - 1

    while left < right:
        if s[left] != s[right]:
            return False
        left += 1
        right -= 1

    return True

print(is_palindrome("racecar"))
print(is_palindrome("hello"))

True
False

On "racecar" the loop starts by comparing indexes 0 and 6, then moves inward 1 step at a time to 1 and 5 and finally to 2 and 4. After that left and right both sit at 3, the while test fails, and the middle e needs no partner. On "hello" the very first comparison of h against o returns False. The 3 letters between them are never read.

Pair sums on a sorted list

A list of track lengths in minutes is sorted ascending, and a 10-minute ad-free gap should be filled by exactly 2 tracks. Start left at the shortest track and right at the longest, then add them. A total below the target can only grow if left moves up to a longer track, and a total above it can only shrink if right moves down to a shorter one.

def pair_with_sum(values, target):
    left = 0
    right = len(values) - 1
    while left < right:
        total = values[left] + values[right]
        if total == target:
            return values[left], values[right]
        if total < target:
            left += 1
        else:
            right -= 1
    return None

durations = [2, 3, 4, 6, 7, 9]
print(pair_with_sum(durations, 10))
print(pair_with_sum(durations, 14))
print(pair_with_sum(durations, 16))

Output:

(3, 7)
None
(7, 9)

Why a move never skips the answer

Take the trace above for a target of 10. Step 1 computes 2 + 9 = 11 and overshoots. Since 2 is the shortest track still in play, every other partner for 9 would overshoot by more, so 9 belongs to no valid pair and dropping it loses nothing. Step 2 is the mirror case: 2 + 7 = 9 falls short, 7 is the longest track still in play, so 2 has no partner left that reaches 10.

Every step removes one value with proof that it cannot be in any valid pair, which is why the input must be sorted. On unsorted values values[left] is no longer guaranteed to be the shortest track still in play. Without that guarantee the loop can walk past a pair that exists.

Pointers moving the same way

Pointers can also travel in the same direction. To remove duplicates from a sorted list in place, a read index visits every item while a write index marks where the next distinct value goes. Sorting already put equal values next to each other, so a value is new exactly when it differs from the last value written.

def dedupe_sorted(values):
    write = 1
    for read in range(1, len(values)):
        if values[read] != values[write - 1]:
            values[write] = values[read]
            write += 1
    del values[write:]
    return values

print(dedupe_sorted([1, 1, 2, 3, 3, 3, 5]))

Output:

[1, 2, 3, 5]

Trace it on [1, 1, 2, 3, 3, 3, 5]. Both indexes start at 1. The 1 at position 1 equals the last value written, values[0], so it's skipped and only read advances. The 2 at position 2 differs, so it's copied to position 1 and write becomes 2. The first 3 lands at position 2, the next 2 copies of 3 match it and are skipped, and 5 lands at position 3. write ends at 4, and del values[write:] cuts the 3 stale items at positions 4 to 6. write never passes read, so a copy never overwrites a value that hasn't been read yet.

What does this print, and how many totals does the loop compute before it stops?

def pair_with_sum(values, target):
    left = 0
    right = len(values) - 1
    while left < right:
        total = values[left] + values[right]
        if total == target:
            return values[left], values[right]
        if total < target:
            left += 1
        else:
            right -= 1
    return None

print(pair_with_sum([1, 4, 5, 8, 11], 13))

• None, since the pointers cross before any total reaches 13
• (4, 8) after 3 totals, the third total being 4 + 8
• (5, 8) after 4 totals: 12, 15, 12, then 13
• (5, 8) after 2 totals, because 11 and then 1 are dropped

Each branch moves the pointer whose value caused the miss. A total below the target means the smaller value is too small, so left steps up to a larger one; a total above it means the larger value is too big, so right steps down. Swap the 2 moves and the walk heads away from the answer: on [2, 3, 4, 6, 7, 9] with a target of 10, the first total of 11 moves left up to the 3, and the totals climb to 12 and 13, then to 15 and 16, until the pointers meet and the function returns None.

About this lesson

This section is part of the Problem Solving: Advanced lesson on DataDriven, the home of data engineering. Lessons cover SQL, Python, Spark, data modeling and pipeline architecture, and each section pairs its explanation with worked examples and practice you run as you go.