From both ends toward the middle
Picture checking whether a word reads the same backwards. You don’t write it out reversed. You put one finger on the first letter and one on the last, compare, then move both fingers one step toward the middle. If every pair matches until the fingers meet, it’s a palindrome.
Those fingers are the two pointers: two variables holding indices into the same array or string. There are two common shapes:
- From both ends toward the middle: palindromes, pairs in a sorted array, reversing.
- Both from the start, at different speeds: one pointer reads every element, the other marks where to write, for cleaning up an array in place.
Two pointers is a way to search a 2-D space of pairs (i, j) in linear time by exploiting monotonic structure: when the input is sorted (or the condition is monotonic in each index), each comparison lets you discard an entire row or column of candidate pairs. The other family, read/write (fast/slow) pointers, compacts or partitions in place with O(1) extra space.
What interviewers probe at senior level: why moving a given pointer is safe (the invariant), handling duplicates without losing or repeating answers, overflow in sums, and extending the idea to k-sum and to problems where it doesn’t apply (unsorted input with no monotonic condition). Those are in the Detailed version.
Valid Palindrome
A phrase is a palindrome if, after converting uppercase letters to lowercase and removing everything that isn’t a letter or a digit, it reads the same forward and backward. Given a string s, return true if it’s a palindrome.
"A man, a plan, a canal: Panama" → true ("amanaplanacanalpanama")
"race a car" → false ("raceacar")
" " → true (empty after cleaning)›
Start one pointer at the beginning and one at the end. What should happen when a pointer is on a space or a comma?
›
Skip characters that aren’t letters or digits by moving that pointer inward, then compare the two characters in lowercase. Stop when the pointers meet.
SolutionTry it yourself firstTime O(n)Space O(1)
Move the left pointer forward and the right pointer backward past anything that isn’t a letter or digit, compare, and step both inward. Any mismatch means it’s not a palindrome.
func isPalindrome(_ s: String) -> Bool {
let chars = Array(s) // Swift strings can't be indexed by Int
var left = 0
var right = chars.count - 1
while left < right {
while left < right && !(chars[left].isLetter || chars[left].isNumber) { left += 1 }
while left < right && !(chars[right].isLetter || chars[right].isNumber) { right -= 1 }
if chars[left].lowercased() != chars[right].lowercased() { return false }
left += 1
right -= 1
}
return true
}fun isPalindrome(s: String): Boolean {
var left = 0
var right = s.length - 1
while (left < right) {
while (left < right && !s[left].isLetterOrDigit()) left++
while (left < right && !s[right].isLetterOrDigit()) right--
if (s[left].lowercaseChar() != s[right].lowercaseChar()) return false
left++
right--
}
return true
}boolean isPalindrome(String s) {
int left = 0, right = s.length() - 1;
while (left < right) {
while (left < right && !Character.isLetterOrDigit(s.charAt(left))) left++;
while (left < right && !Character.isLetterOrDigit(s.charAt(right))) right--;
if (Character.toLowerCase(s.charAt(left)) != Character.toLowerCase(s.charAt(right))) return false;
left++;
right--;
}
return true;
}function isPalindrome(s: string): boolean {
const isAlnum = (c: string) => /[a-z0-9]/i.test(c);
let left = 0;
let right = s.length - 1;
while (left < right) {
while (left < right && !isAlnum(s[left])) left++;
while (left < right && !isAlnum(s[right])) right--;
if (s[left].toLowerCase() !== s[right].toLowerCase()) return false;
left++;
right--;
}
return true;
}Swift note
Swift’s String uses String.Index, not integers, because characters have different sizes in memory. Converting to Array(s) costs O(n) extra space but makes integer indexing O(1). You can stay O(1) in space by walking s.startIndex and s.index(before: s.endIndex) with index(after:) and index(before:).
TypeScript note
s[i] reads one UTF-16 code unit, which is fine for this ASCII check. For text in any language, test with a Unicode property regex (the u flag with letter and number classes), and remember that emoji and some accented letters span two units.
Why moving a pointer is safe
Picture all pairs (i, j) with i < j of a sorted array as the upper triangle of a matrix whose values grow to the right and downward. Starting at (0, n − 1), the top-right corner:
- If
nums[i] + nums[j] < target, then every pair (i, k) with k ≤ j is also too small, sincenums[k] ≤ nums[j]. The whole row i is eliminated:i += 1. - If the sum is too big, every pair (k, j) with k ≥ i is too big: the whole column j is eliminated:
j -= 1.
Each step discards a row or a column, so after at most n − 1 steps every pair has been either checked or ruled out. Saying this out loud is what separates “I memorized it” from “I can adapt it”, and it’s the argument you need for variants like Container With Most Water (move the shorter wall: the taller one can’t produce a bigger area with a narrower width).
When the sum doesn’t fit
Predict the output
What does this print?
let a = 2_000_000_000
let b = 2_000_000_000
print(a + b > 0)val a = 2_000_000_000
val b = 2_000_000_000
println(a + b > 0)int a = 2_000_000_000;
int b = 2_000_000_000;
System.out.println(a + b > 0);const a = 2_000_000_000;
const b = 2_000_000_000;
console.log(a + b > 0);Swift's Int is 64-bit on iPhone, Mac and Linux (older Apple Watch models are the exception, at 32 bits), so 4,000,000,000 fits and the result is true. With Int32 the addition traps (crashes) instead of wrapping, since Swift checks overflow by default.
Int is 32-bit: 2,000,000,000 + 2,000,000,000 wraps around to -294,967,296, so the comparison is false. In a two-pointer loop, a wrapped sum moves the wrong pointer and silently returns a wrong answer. Use Long for sums, or compare a > target - b.
int is 32-bit: the sum overflows to -294,967,296 without any error, so it prints false. Use long sums, Math.addExact to fail loudly, or rearrange the comparison to avoid adding.
Numbers are 64-bit floating point, exact for integers up to Number.MAX_SAFE_INTEGER (2⁵³ − 1), so 4,000,000,000 is fine: true. The risk is different: far beyond 2⁵³ sums lose precision silently (2 53 + 1 === 2 53). Use BigInt for values that large.
- Explain the invariant: on sorted data, a too-small sum eliminates the whole row of pairs with the current left element, so moving left is safe (and a too-big sum eliminates a column). Container With Most Water: move the shorter wall.
Kotlin, Java
32-bit Int/int sums wrap silently near 2 billion: use Long sums, Math.addExact, or compare a > target - b.
Swift
Int is 64-bit on iPhone and Mac, and overflow traps instead of wrapping; with Int32 input, a big sum crashes rather than giving a wrong answer.
TypeScript
Numbers are doubles: sums are exact only up to Number.MAX_SAFE_INTEGER (2⁵³ − 1), then lose precision silently. Use BigInt beyond that. Strings index UTF-16 units, so emoji take two positions.
Check this part
Where do the two pointers start when checking a palindrome?
In "A man, a plan…", the left pointer lands on a space. What does the check do?
Why can you discard a whole row of pairs when the sum is too small?
let a = 2_000_000_000, b = 2_000_000_000; print(a + b > 0)prints…val a = 2_000_000_000; val b = 2_000_000_000; println(a + b > 0)prints…int a = 2_000_000_000, b = 2_000_000_000; System.out.println(a + b > 0);prints…const a = 2_000_000_000, b = 2_000_000_000; console.log(a + b > 0)prints…