1. Palindrome Number (LeetCode)
Model answer
The task
Determine whether an integer reads the same from left to right and right to left. Negative values are not palindromes.
Key idea
Reverse only the last half of the digits, then compare it with the remaining first half. This avoids converting to a string and keeps the extra space constant.
Approach
- Return
Falsefor negative integers. - Return
Falsefor positive integers ending in zero; zero itself is a palindrome. - Repeatedly move the last digit from the number to a reversed-half accumulator.
- Stop when the accumulator has at least as many digits as the remaining number.
- Compare the halves directly for even digit counts, or discard the middle digit for odd counts.
class Solution:
def isPalindrome(self, x: int) -> bool:
# Negative numbers have a leading minus sign, so they cannot be palindromes.
if x < 0:
return False
# A positive number ending in zero would need a leading zero to be palindromic.
if x != 0 and x % 10 == 0:
return False
reversed_half = 0
# Move digits until the reversed half is at least as long as the remaining half.
while x > reversed_half:
reversed_half = reversed_half * 10 + x % 10
x //= 10
# For an odd number of digits, ignore the middle digit.
return x == reversed_half or x == reversed_half // 10
Complexity:
- Time: O(log₁₀ n), for processing the digits of the number.
- Space: O(1), using only a few integer variables.
Common follow-ups
- How would you check a palindrome by converting to a string? Compare symmetric characters, using O(log n) extra space.
- How would you avoid integer overflow in a fixed-width language? Reversing only half the digits keeps the accumulator bounded.
- What about zero and numbers ending in zero? Zero is palindromic; other numbers ending in zero are not.