Valid Palindrome
Two pointers converging from both ends
time O(n)space O(1)
A palindrome mirrors around its center: the first char must equal the last, the second the second-last, and so on inward. Two pointers start at the two ends and walk toward the middle comparing one mirrored pair per step, so the check is O(n) time and O(1) space with no reversed copy.
Details
Animated on: Decide whether a string reads the same forwards and backwards.
Problem:Valid PalindromeEasy
Two pointers converging from both ends
step 1 / 11
r
[0]a
[1]c
[2]e
[3]c
[4]a
[5]r
[6]The word 'racecar' as characters (indices 0..6). We must decide if it reads the same left-to-right and right-to-left.
Pseudocode
1FUNCTION isPalindrome(s): // s = 'racecar'2 l = 0; r = length of s - 13 WHILE l < r:4 IF s[l] != s[r]: RETURN false5 l = l + 16 r = r - 17 RETURN true
← / → step · space play · Home restart
Every step in words
Show all 11 steps
- The word 'racecar' as characters (indices 0..6). We must decide if it reads the same left-to-right and right-to-left.
- Place l on the first char and r on the last. A palindrome's outermost chars must match, so we test them as a pair.
- l (0) < r (6) is true, so there is still an untested pair between the pointers — enter the loop.
- Compare s[l]='r' with s[r]='r'. If they differed we would return false right here.
- 'r' == 'r' — the outer pair mirrors, so lock it green and step both pointers inward to l=1, r=5.
- l (1) < r (5) still holds. Compare the next mirrored pair: s[l]='a' with s[r]='a'.
- 'a' == 'a' — confirmed. Advance inward to l=2, r=4.
- l (2) < r (4) holds. Compare s[l]='c' with s[r]='c'.
- 'c' == 'c' — confirmed. Advance to l=3, r=3; the pointers now land on the same cell.
- l (3) < r (3) is false — the pointers met at the lone middle char 'e', which has no partner to test. The loop ends.
- Every mirrored pair matched and nothing came back unequal — 'racecar' is a valid palindrome. Return true.
Now solve it yourself
Watching is the first half. The second is writing it without the animation.