Palindrome Check
Algorithm · Starter
Step through it: Two Pointers pattern
target = 10
Step 1 of 6
Goal: find two numbers in this sorted list that add up to 10. Trying every pair is slow. Instead, put one marker at each end of the list.
Step 2 of 6
Add the two marked numbers: 1 + 11 = 12. That is more than 10, so the sum is too big.
Step 3 of 6
To make the sum smaller we need a smaller right number, and everything left of 11 is smaller. 11 can never be part of the answer, so cross it out and move the right marker in.
Step 4 of 6
Now 1 + 8 = 9, which is too small. To make it bigger we need a bigger left number, so cross out 1 and move the left marker in.
Step 5 of 6
2 + 8 = 10. Found it. Every move crossed out one number for good, so we look at each number at most once. Two markers closing in on each other is called two pointers, and it works because the list is sorted.
Step 6 of 6
Your turn. The target is now 14. Look at the sum, then choose which marker to move.
A Palindrome is a string that reads the same forwards and backwards. This means that the second half of the string is the reverse of the first half.
Examples
The following are palindromes (thus would return TRUE):
- "a"
- "pop" -> p + o + p
- "deed" -> de + ed
- "kayak" -> ka + y + ak
- "racecar" -> rac + e + carThe following are NOT palindromes (thus would return FALSE):
- "rad"
- "dodo"
- "polo"Code
/**
* @param {string} string
* @return {boolean}
*/
export default function isPalindrome(string) {
let left = 0;
let right = string.length - 1;
while (left < right) {
if (string[left] !== string[right]) {
return false;
}
left += 1;
right -= 1;
}
return true;
}References
Practice
Two Pointers
- Valid PalindromeEasy
- Two Sum II - Input Array Is SortedEasy
- Remove Duplicates from Sorted ArrayEasy
- Move ZeroesEasy
- Squares of a Sorted ArrayEasy
- Reverse StringEasy
- Merge Sorted ArrayEasy
- Remove ElementEasy
- 3SumMedium
- 3Sum ClosestMedium
- Container With Most WaterMedium
- Sort ColorsMedium
- Remove Duplicates from Sorted Array IIMedium
- Valid Palindrome IIMedium
- Boats to Save PeopleMedium
- Partition LabelsMedium
- 4SumMedium
- 3Sum SmallerMedium
- Trapping Rain WaterHard
String Matching
- Find the Index of the First Occurrence in a StringEasy
- Repeated Substring PatternEasy
- Is SubsequenceEasy
- Rotate StringEasy
- Longest Palindromic SubstringMedium
- Palindromic SubstringsMedium
- Repeated String MatchMedium
- One Edit DistanceMedium
- Shortest PalindromeHard
- Longest Happy PrefixHard
- Longest Duplicate SubstringHard
- Edit DistanceHard
- Wildcard MatchingHard
Spotted a mistake or something unclear? Report it on GitHub.