Two pointers, walking inward

The simplest version of the pattern, and the habit of naming what is already settled.

Key idea

The shape

One pointer starts at the left end, one at the right, and they move toward each other until they meet. Each pass compares the two ends and decides what to do next.

Because the pointers only ever move inward, the whole thing is one linear pass no matter how the moves are distributed. Every step retires at least one position, and there are only n positions.

1def trim_matching_ends(text):2    """Strip off the matching prefix and suffix, return whatever is left."""3    left, right = 0, len(text) - 14    while left < right and text[left] == text[right]:5        left += 16        right -= 17    return text[left:right + 1]8 9print(trim_matching_ends("abcba"))10print(trim_matching_ends("abcde"))

Skipping positions you do not care about

A common variation is that only some positions count. Rather than building a cleaned copy of the input, advance each pointer past the characters that do not matter and work with what is left.

This keeps the extra space at O(1), which is usually the reason the problem is being asked in the first place. Below, only letters move; everything else stays exactly where it started.

1def reverse_letters_only(text):2    chars = list(text)3    left, right = 0, len(chars) - 14    while left < right:5        while left < right and not chars[left].isalpha():6            left += 17        while left < right and not chars[right].isalpha():8            right -= 19        chars[left], chars[right] = chars[right], chars[left]10        left += 111        right -= 112    return "".join(chars)13 14print(reverse_letters_only("a-bC-dEf-ghIj"))15print(reverse_letters_only("....."))

Predict the output· 5 min

Predict the output: a missing bound

The inner skip loop has no bound of its own. Type what this prints, including the exception name if it raises one.

Python

1def broken(text):2    chars = list(text)3    left, right = 0, len(chars) - 14    while left < right:5        while not chars[left].isalpha():6            left += 17        while not chars[right].isalpha():8            right -= 19        chars[left], chars[right] = chars[right], chars[left]10        left += 111        right -= 112    return "".join(chars)13 14try:15    print(broken(".,.,"))16except IndexError:17    print("IndexError")

Printed output

Code lab· 18 min

Converging pointer drills

Three functions on the same skeleton. pair_sums_from_ends pairs the outermost values, then the next pair inward, and so on. count_matching_ends counts how many pairs of characters match while walking inward, stopping at the first mismatch. has_pair_summing_to takes a sorted list and reports whether any two values add to the target.

solution.py

Tests

print(pair_sums_from_ends([1, 2, 3, 4]), pair_sums_from_ends([1, 2, 3]), pair_sums_from_ends([5]))print(count_matching_ends("abcba"), count_matching_ends("abcda"), count_matching_ends("xy"))print(has_pair_summing_to([1, 3, 5, 8], 11), has_pair_summing_to([1, 3, 5, 8], 12))

Output

Run tests to see output.

Problem· 14 min

Valid Palindrome

Read the constraints first and let them tell you what complexity is expected. Derive the approach, implement it, run the tests, and submit when it passes.

Skipping positions you do not care about

A common variation is that only some positions count. Rather than building a cleaned copy of the input, advance each pointer past the characters that do not matter and work with what is left.

This keeps the extra space at O(1), which is usually the reason the problem is being asked in the first place. Below, only letters move; everything else stays exactly where it started.

1def reverse_letters_only(text):2    chars = list(text)3    left, right = 0, len(chars) - 14    while left < right:5        while left < right and not chars[left].isalpha():6            left += 17        while left < right and not chars[right].isalpha():8            right -= 19        chars[left], chars[right] = chars[right], chars[left]10        left += 111        right -= 112    return "".join(chars)13 14print(reverse_letters_only("a-bC-dEf-ghIj"))15print(reverse_letters_only("....."))

1def broken(text):2 chars = list(text)3 left, right = 0, len(chars) - 14 while left < right:5 while not chars[left].isalpha():6 left += 17 while not chars[right].isalpha():8 right -= 19 chars[left], chars[right] = chars[right], chars[left]10 left += 111 right -= 112 return "".join(chars)13 14try:15 print(broken(".,.,"))16except IndexError:17 print("IndexError")

print(pair_sums_from_ends([1, 2, 3, 4]), pair_sums_from_ends([1, 2, 3]), pair_sums_from_ends([5]))print(count_matching_ends("abcba"), count_matching_ends("abcda"), count_matching_ends("xy"))print(has_pair_summing_to([1, 3, 5, 8], 11), has_pair_summing_to([1, 3, 5, 8], 12))