Two Pointers
How Two Pointers work
Before you start
- Open lesson
Arrays & Strings
Two pointers are two indexes into one array or string. You should be comfortable reading s[i] in O(1).
Why it matters
Text validators often need to ignore formatting while checking whether content reads the same in reverse. Building cleaned and reversed copies doubles memory for data that may already be large. For "Top spot!", the solution must ignore punctuation, spaces, and case in one pass with O(1) extra space.
Example
Valid Palindrome
A phrase is a palindrome if, after lowercasing and dropping non-alphanumeric characters, it reads the same forward and backward. Return whether s is a palindrome.
- Input
- s = "Top spot!"
- Output
- True
Approach 2 · Resolve the bottleneck
The idea
Keep one example in view
Valid Palindrome
s = "Top spot!"→True
The baseline, Clean a copy and reverse it, is O(n) · O(n). The better model below keeps this exact input and removes that bottleneck.
In "Top spot!", "T" pairs with "t", "o" with "o", and the space and "!" do not count. Instead of allocating a cleaned string and its reverse, inspect matching positions in the original text.
In "Top spot!", left starts on "T" and right starts on "!". Skip "!", then compare "T" with "t" after lowering their case. They match, so both ends move inward.
The next pairs are "o" with "o" and "p" with "p". When left reaches the space, skip it; the pointers then meet at "s". Every move discards a character that is either irrelevant or already matched, so no character needs a second visit.
Pro
The rest of this is on Pro
The idea above is free. The walkthrough, the cost, and the practice are on Pro.