Converging Pointers: Checking From Both Ends
A sign-maker wants to know whether a slogan reads the same forwards and backwards once spaces, punctuation and capital letters are ignored. "Top, spot!" does. The obvious fix is to clean the text, reverse it and compare, which builds two new strings. Two fingers, one at each end of the original text, can do the same check without copying anything.
The rule
Start at both ends, compare, and walk inward until they meet.
Put left on the first character and right on the last. At each step, either skip a character that does not count, or compare the two characters that do. A mismatch ends the check at once; a match moves both pointers one step inward.
def reads_same_both_ways(text):
left, right = 0, len(text) - 1
while left < right:
if not text[left].isalnum():
left += 1 # skip punctuation or a space
elif not text[right].isalnum():
right -= 1
elif text[left].lower() != text[right].lower():
return False # a real mismatch
else:
left += 1 # a match: both step inward
right -= 1
return TrueEvery step moves at least one pointer, and they never cross, so the loop runs at most n times. Nothing is copied, so the extra memory is constant: two integers. When the pointers meet, every pair has matched, and a single leftover middle character has nothing to be compared with.
This is the first of two pointer shapes. Converging pointers start at the two ends and move toward each other, as here. Same-direction pointers both start at the left, with one running ahead of the other; you will meet that shape again inside sliding windows.
The shortcut
At each step ask one question with three possible answers: "Skip, fail, or match?" Skip moves one pointer, fail returns False, match moves both. The loop ends when the pointers meet.
T and !
!is not a letter or digit: skip it, andrightmoves tot.
The clean-and-reverse version is still a fine first answer, and saying it out loud first is good interview practice: keep the lower-cased letters and digits in a list, then compare the list with its reverse. It costs a copy of the text; the pointers are the follow-up that removes it.
The trap is forgetting a skip. Compare the comma with a letter and a perfectly good slogan fails.
Drills
Answer fast — trust the rule.
What does reads_same_both_ways("Ab, a") return?
What does reads_same_both_ways("Step on it") return?
How much extra memory does the two-pointer check use?
What does it return for an empty string, and why?
Remember
- Start at both ends, compare, and walk inward until they meet.
- Shortcut: skip, fail, or match; match moves both pointers.
- Trap: comparing a space or punctuation mark instead of skipping it.