LeetCode 125 Explained: Valid Palindrome Using Two Pointers in Python

Problem Overview

In this problem, we are given a string that may contain letters, numbers, spaces, and special characters. Our task is to determine whether the string is a valid palindrome after removing all non-alphanumeric characters and ignoring letter case.

Key Observations

• Only letters (a–z, A–Z) and digits (0–9) matter.
• Uppercase and lowercase letters should be treated as equal.
• The original order of characters must be respected.

Optimal Strategy: Two Pointer Technique

Instead of creating a new filtered string, we use two pointers to scan the original string from both ends. This allows us to validate the palindrome in a single pass while using constant extra space.

How the Algorithm Works

1. Initialize two pointers:
   • Left pointer at the start of the string
   • Right pointer at the end of the string
2. Move the left pointer forward until it points to an alphanumeric character.
3. Move the right pointer backward until it points to an alphanumeric character.
4. Compare the characters at both pointers after converting them to lowercase.
5. If they match, move both pointers inward and continue.
   If they do not match, the string is not a palindrome.
6. If all valid characters match, return true.

Why This Approach Is Optimal

• Time Complexity: O(n) — each character is visited at most once.
• Space Complexity: O(1) — no additional data structures are used.
• Avoids unnecessary memory allocation caused by string preprocessing.

Two Pointer Pattern Summary

The two-pointer pattern is a powerful technique used when a problem involves traversing a sequence from both ends. It is especially effective when comparisons or condition checks are required between elements at symmetric positions.

When to Use Two Pointers

• Palindrome checks (strings or arrays)
• Removing duplicates from sorted arrays
• Reversing arrays or strings in-place
• Finding pairs with a given condition (sum, difference, etc.)
• Partitioning problems

Common Two Pointer Variants

• Opposite-direction pointers: One starts from the beginning, the other from the end.
• Same-direction pointers: Both move forward but at different speeds.
• Fast & Slow pointers: Often used in cycle detection and linked list problems.

Why Two Pointers Are Important

This pattern helps convert brute-force solutions into optimal ones by reducing time complexity from O(n²) to O(n) and minimizing space usage. Mastering this pattern is essential for solving array and string problems efficiently in coding interviews.