#10 Easy Time O(n) Space O(1) Animated

Valid Palindrome

A string is a palindrome if, after lowercasing and removing non-alphanumerics, it reads the same forwards and backwards.

LeetCode ↗

Tutor Mode Build the mental model before you memorize the code.

1 Predict
2 Trace
3 Explain
4 Implement

Pattern Two pointers shrink the search space

Use ordering or symmetry to decide which boundary can move without discarding a valid answer.

Approach: Two Pointers — In Place

Click play to start

Step 0 / 0

Press play to start the visualization.

1×

Core Insight

Use ordering or symmetry to decide which boundary can move without discarding a valid answer.

Common Pitfall

Move the pointer justified by the comparison; moving both can skip a valid pair.

Description

A string is a palindrome if, after lowercasing and removing non-alphanumerics, it reads the same forwards and backwards.

Constraints

Time Complexity: O(n)
Space Complexity: O(1)

Solution — Two Pointers — In Place

TimeO(n) SpaceO(1)

Implementation Plan

Translate the invariant into these small, testable moves.

Place pointers at the relevant boundaries.
Evaluate the pair or window.
Use the comparison to move exactly one boundary.
Stop when the pointers cross or the target is found.

def isPalindrome(s):
    left, right = 0, len(s) - 1  # line 1
    while left < right:           # line 2
        while left < right and not s[left].isalnum():  # line 3
            left += 1              # line 4
        while left < right and not s[right].isalnum():  # line 5
            right -= 1             # line 6
        if s[left].lower() != s[right].lower():  # line 7
            return False           # line 8
        left += 1                  # line 9
        right -= 1                 # line 10
    return True                    # line 11

Two Sum II - Input Array Is Sorted

Valid Palindrome

Steps

Description

Constraints

Tags

Solution — Two Pointers — In Place