125. Valid Palindrome

Quick Identifier

Topic: two-pointers
Pattern: inward convergence with skipping
Difficulty: Easy
Companies: Amazon, Google, Meta, Microsoft, Apple
Frequency: High
LeetCode: 125
Hint: Skip characters that do not matter, then compare the meaningful left and right characters.

Quick Sights

Time Complexity: O(n) - every character is skipped or compared at most once.
Space Complexity: O(1) - no cleaned copy is needed.
Core Mechanism: Move left/right inward, skipping non-alphanumeric characters and comparing normalized values.

Concept Explanation

A palindrome proof settles pairs from the outside in. Everything outside the current window has either matched or been ignored.

Spaces and punctuation are not part of the problem, so the pointers skip them before comparing. Once a pair matches, both characters are permanently settled and the window shrinks.

Diagram

This diagram shows the pointer decisions and the step-by-step algorithm flow.

Loading diagram…

Study Pattern (SDE3+)

0-3 min: Name the pointer shape, then state the invariant and discard rule before coding.
Implementation pass: Keep pointer movement explicit; every branch must return, record an answer, or move at least one pointer.
5 min extension: Explain how the solution changes for immutable input, streaming input, many duplicate values, or many repeated queries.

Approaches

Filter and reverse is simple but O(n) space. Two pointers on the original string keep O(1) space.

Optimal Solution

JavaScript

function isPalindrome(text) {
	let left = 0, right = text.length - 1;
	while (left < right) {
		while (left < right && !/[a-zA-Z0-9]/.test(text[left])) left++;
		while (left < right && !/[a-zA-Z0-9]/.test(text[right])) right--;
		if (text[left].toLowerCase() !== text[right].toLowerCase()) return false;
		left++; right--;
	}
	return true;
}

Go

func isPalindrome(s string) bool {
	left, right := 0, len(s)-1
	for left < right {
		for left < right && !isAlnum(s[left]) { left++ }
		for left < right && !isAlnum(s[right]) { right-- }
		if toLower(s[left]) != toLower(s[right]) { return false }
		left++
		right--
	}
	return true
}

func isAlnum(b byte) bool {
	return (b >= 'a' && b <= 'z') || (b >= 'A' && b <= 'Z') || (b >= '0' && b <= '9')
}

func toLower(b byte) byte {
	if b >= 'A' && b <= 'Z' { return b + 'a' - 'A' }
	return b
}