Two pointers
The two-pointer pattern keeps two positions and moves them according to a rule, so each item is visited once: O(n) where a pair of nested loops would be O(n²).
- From both ends: start one pointer at the front and one at the back and move them toward each other. That checks palindromes, and finds a pair with a given sum in sorted data: if the sum is too small, move the left pointer right; too big, move the right pointer left.
- Side by side: one pointer per list, always advancing the one with the smaller value. That merges two sorted lists, finds common items, or matches each record to its nearest neighbor in another sorted list.
The key questions are what each pointer means and when it moves. Write them down in a comment before coding. Edge cases to test on purpose: empty lists, one item, all items equal.
def has_pair(sorted_vals, target):
i, j = 0, len(sorted_vals) - 1
while i < j:
s = sorted_vals[i] + sorted_vals[j]
if s == target:
return True
if s < target:
i += 1
else:
j -= 1
return False
has_pair([10, 25, 40, 75], 100), has_pair([10, 25], 100)
Out: (True, False). Each step rules out one value for good.