Two Pointers · LC #125
Valid Palindrome
Use two inward-moving pointers to verify a string is a palindrome after stripping non-alphanumeric characters and lowercasing. Canonical intro to the two-pointer pattern.
Statement
Problem & Approach
Problem statement, sample I/O, and key reasoning.
A phrase is a palindrome if, after converting all uppercase letters to lowercase and removing all non-alphanumeric characters, it reads the same forward and backward. Given string `s`, return `true` if it is a palindrome.
Sample I/O
Input: s = "A man, a plan, a canal: Panama"
Output: true ("amanaplanacanalpanama")
Input: s = "race a car"
Output: falseTime: O(n) · Space: O(1)
Intuition
How to Think About It
Intuition
A palindrome mirrors around its center. By placing one pointer at each end and walking inward, we can compare characters symmetrically without allocating a reversed copy - as long as we skip non-alphanumeric noise.
Core Concept
Place `l = 0`, `r = len-1`. Advance `l` past non-alphanumeric chars; retreat `r` the same way. Compare `lower(s[l])` vs `lower(s[r])`; if they differ return false, else move both inward. Stop when `l >= r`. Alternatively: clean the string first then compare to its reverse.
When to use
Any symmetric string or array check - palindrome detection, two-sum on sorted array, container problems, reversal tasks.
When NOT to use
When you need all palindromic substrings (use expand-around-center or Manacher). When the string is too large to clean in-place and memory matters.
Key Insights
What to Know Cold
- The in-place two-pointer approach uses O(1) extra space; the clean-then-compare one-liner uses O(n).
- Always skip non-alphanumeric characters on BOTH sides before each comparison.
- Lowercasing must happen at comparison time, not during pointer advancement.
- An empty string or single character is always a palindrome - the while condition `l < r` handles it naturally.
- This exact pointer-skip pattern reappears in 3Sum duplicate-skipping and merge-sorted problems.
1 example
Worked Examples
Two-Pointer In-Place
"A man, a plan, a canal: Panama" - verify palindrome without extra allocation.
l starts at 0, r at end. Skip non-alphanumeric on both sides, compare lowercased chars, move inward. All pairs match → true.
def isPalindrome(s: str) -> bool:
l, r = 0, len(s) - 1
while l < r:
while l < r and not s[l].isalnum(): l += 1
while l < r and not s[r].isalnum(): r -= 1
if s[l].lower() != s[r].lower():
return False
l += 1; r -= 1
return TrueDemonstrates the skip-and-compare two-pointer pattern - O(n) time, O(1) space - the foundation for Container With Most Water, 3Sum, and sorted-array pair problems.