Coding interview problems › Two Pointers

↔️ Two Pointers Easy

Valid Palindrome

Valid Palindrome explained: two pointers walk inward, skipping non-alphanumeric characters and ignoring case, in O(n) time, O(1) space. Tested Python.

Also searched as: check palindrome string ignoring non-alphanumeric · palindrome two pointers

↔️

Try it live Free

Two Pointers

Watch two pointers replace a double loop with one inward sweep. The same move-from-both-ends idea checks a palindrome in a single pass.

Open the playground →

The problem

Given a string, decide whether it reads the same forwards and backwards after you ignore case and skip every character that is not a letter or digit.

Input"A man, a plan, a canal: Panama"
OutputTrue
Input"race a car"
OutputFalse

The key insight

A palindrome mirrors around its centre, so compare the outermost characters and move inward. Two pointers, one at each end, do this without building a cleaned copy: each pointer skips junk characters, then the two characters must match ignoring case.

Brute force first: Building a filtered lowercase copy and comparing it with its reverse is also O(n), but uses O(n) extra space.

Step-by-step approach

  1. Put i at the start and j at the end.
  2. Move i right while it points at a non-alphanumeric character; move j left likewise.
  3. Compare s[i].lower() with s[j].lower(); if they differ, return False.
  4. Step both pointers inward and repeat while i < j.
  5. If they meet without a mismatch, return True.

Python solution

PYTHON 3tested
def is_palindrome(s):
    i, j = 0, len(s) - 1
    while i < j:
        while i < j and not s[i].isalnum():
            i += 1
        while i < j and not s[j].isalnum():
            j -= 1
        if s[i].lower() != s[j].lower():
            return False
        i += 1
        j -= 1
    return True

Complexity

TimeO(n)
SpaceO(1)

Each pointer moves only inward, so together they visit each character at most once. No copy of the string is made.

Common mistakes

Frequently asked questions

What is the time and space complexity of Valid Palindrome?

The two-pointer solution is O(n) time and O(1) extra space. Building a cleaned reversed copy is O(n) time and O(n) space.

Is an empty string a palindrome?

Yes. With nothing to compare there is no mismatch, so the function returns True, and so does a string with only punctuation.

What if I may delete at most one character?

On the first mismatch, check whether skipping the left character or the right character leaves a palindrome. That stays O(n).

Preparing for placements?

Take the 2-minute readiness check to find your weak patterns, then follow the placement path from DSA core to system design.

📋 2-minute readiness check The full placement path

All coding interview problems More Two Pointers Two Pointers lab Placement prep guides

Problem statements on this site are written in our own words. Problem names are the common names used across interview-prep communities; BitBootcamp is an independent learning platform and is not affiliated with LeetCode or any company that asks these questions.