Valid Palindrome - two pointers that walk toward each other

Day 33 moved two pointers in the same direction (match in order). Today they converge from both ends — with skip logic for characters that don’t count. First Two Pointers problem on the NeetCode roadmap.

A string is a palindrome if it reads the same forward and backward — but only letters and digits count, and case doesn’t matter. “A man, a plan, a canal: Panama” is a palindrome. “race a car” is not. The interview pattern: compare from both ends, skip what doesn’t count, exit early on mismatch.

The problem

isPalindrome("A man, a plan, a canal: Panama") → true
isPalindrome("race a car") → false
isPalindrome(" ") → true  // empty after cleanup

The trap: punctuation, spaces, and case. You can’t just reverse the raw string — you need to decide which characters matter before comparing.

Approach 1: Clean + reverse + compare

function isPalindrome(s) {
  const clean = s.toLowerCase().replace(/[^a-z0-9]/g, '');
  return clean === clean.split('').reverse().join('');
}

Correct — but it builds two new strings: the cleaned copy and its reverse. O(n) time, O(n) space, and the constant factors hurt at scale.

Approach 2: Clean + two pointers

function isPalindrome(s) {
  const clean = s.toLowerCase().replace(/[^a-z0-9]/g, '');
  let l = 0, r = clean.length - 1;
  while (l < r) {
    if (clean[l] !== clean[r]) return false;
    l++; r--;
  }
  return true;
}

Same cleaning step, then converge from both ends. One allocation instead of two. Still O(n) space for the cleaned copy.

Approach 3: Two pointers on the original — skip inline

function isPalindrome(s) {
  let l = 0, r = s.length - 1;
  while (l < r) {
    while (l < r && !isAlnum(s[l])) l++;       // skip left
    while (l < r && !isAlnum(s[r])) r--;       // skip right
    if (lower(s[l]) !== lower(s[r])) return false;
    l++; r--;
  }
  return true;
}

Zero allocations. The pointers skip punctuation and spaces as they go, compare only real characters, and exit on the first mismatch. This is the interview answer: same O(n) time, O(1) space.

Benchmark — honest constants (Node, 30-run median)

3 approaches × 3 sizes × 2 inputs (palindrome + non-palindrome), 30 runs each, median μs. The benchmark script and standalone write-up are not included in this repository.

Approach	n=1K (μs)	n=10K (μs)	n=100K (μs)
Reverse-compare	31.5	379.3	4,522.9
Filter + two-ptr	14.5	190.4	1,900.6
No-alloc two-ptr	12.5	77.0	723.2

Headline: at n=100K the no-alloc two-pointer is 6.3× faster than reverse-compare and 2.6× faster than filter+two-ptr. All three are O(n) — the win is constant factors: fewer allocations, better cache locality, no reversed copy.

What breaks? — Anti-patterns

1. Reverse the raw string without cleaning. Punctuation and case break the comparison before you start. Fix: define what counts (alphanumeric, case-insensitive) first.

2. Cleaning into a new string when you don’t have to. Two allocations (cleaned + reversed) when zero will do. Fix: skip inline with two pointers on the original.

3. Comparing all n/2 pairs even after a mismatch. The answer is already decided. Fix: return false on the first mismatch — early exit.

4. Forgetting the empty-after-cleanup case. ” ” and ”!!!” are palindromes — empty string reads the same both ways. Fix: the while-loop handles it (l ≥ r → true).

How it connects

• Day 33 (Is Subsequence): two pointers moving in the same direction through different strings — match in order, gaps allowed.
• Day 19 (Product Except Self): directional accumulation (forward + backward passes) — same DNA: information from both ends.
• Day 5 (Valid Anagram): character-level comparison — but anagram compares counts; palindrome compares positions.
• Two Sum II (next): sorted input → converging pointers find the pair in O(n) — same pattern, different goal.

Transfer questions

What you should be able to do

• Write the no-alloc two-pointer solution from memory in under 3 minutes.
• Explain why O(1) space beats O(n) space at the same Big-O — constant factors.
• Name the difference from Day 33: same-direction vs converging pointers.
• Handle edge cases: empty after cleanup, single char, all punctuation.
• Cite the bench: 6.3× at n=100K vs reverse-compare.

Quiz

Your teach step

Close this lesson. Write the “Explain like I’m 10” and the “60-second LinkedIn version” from memory. Focus on: converging pointers, skip logic, O(1) space, and the 6.3× bench. Post it, and paste the link.

Questions? Ask the agent — Valid Palindrome II (one deletion), linked-list palindrome, or Two Sum II setup.