Palindrome Number
EasyPrompt
Given an integer x, return true if x is a palindrome, and false otherwise.
Example 1:
Input: x = 121
Output: true
Explanation: 121 reads as 121 from left to right and from right to left.Example 2:
Input: x = -121
Output: false
Explanation: From left to right, it reads -121. From right to left, it becomes 121-. Therefore it is not a palindrome.Example 3:
Input: x = 10
Output: false
Explanation: Reads 01 from right to left. Therefore it is not a palindrome.
Constraints:
-231 <= x <= 231 - 1
Follow up: Could you solve it without converting the integer to a string?
Approaches
3 approaches with complexity analysis and trade-offs.
The most intuitive approach is to convert the integer into a string. Once we have the string representation, we can easily check if it's a palindrome. This can be done by comparing the string with its reversed version or by using a two-pointer technique.
Algorithm
- Check if the input integer
xis negative. If it is, returnfalse. - Convert the integer
xto a strings. - Initialize two pointers:
left = 0andright = s.length() - 1. - Loop while
left < right: a. If the character atleftis not equal to the character atright, returnfalse. b. Incrementleftand decrementright. - If the loop finishes, the number is a palindrome, so return
true.
Walkthrough
First, we handle the edge case: negative numbers are not palindromes, so if x is less than 0, we return false immediately.
Next, we convert the integer x into its string representation, let's call it s.
We then use two pointers, left starting at the beginning of the string (index 0) and right starting at the end (index s.length() - 1).
We iterate as long as left is less than right, comparing the characters at these two pointers. If at any point s.charAt(left) does not equal s.charAt(right), we know it's not a palindrome and can return false.
In each iteration, we move the pointers closer to the center by incrementing left and decrementing right.
If the loop completes without finding any mismatches, it means the string is a palindrome, and we return true.
class Solution { public boolean isPalindrome(int x) { if (x < 0) { return false; } String s = Integer.toString(x); int left = 0; int right = s.length() - 1; while (left < right) { if (s.charAt(left) != s.charAt(right)) { return false; } left++; right--; } return true; }}Complexity
Time
O(d), where d is the number of digits in x. Converting the number to a string takes O(d) time, and the two-pointer comparison also takes O(d) time.
Space
O(d), for storing the string representation of the number, where d is the number of digits.
Trade-offs
Pros
Very simple and easy to understand.
Leverages built-in string manipulation functionalities.
Cons
Requires extra space proportional to the number of digits to store the string.
Does not meet the 'follow-up' constraint of solving it without string conversion.
This approach avoids string conversion by mathematically reversing the entire integer. We then compare the reversed integer with the original one. If they are identical, the number is a palindrome.
Algorithm
- If
xis negative, returnfalse. - Store the original value of
xin a variable, e.g.,originalX. - Initialize a
longvariablereversedNum = 0to store the reversed number and prevent overflow. - Loop while
xis not 0: a. Get the last digit:digit = x % 10. b. Append the digit to the reversed number:reversedNum = reversedNum * 10 + digit. c. Remove the last digit fromx:x = x / 10. - Compare
originalXwithreversedNum. If they are equal, returntrue; otherwise, returnfalse.
Walkthrough
As with the first approach, we first handle the edge case of negative numbers, which are never palindromes.
We need to keep a copy of the original number, originalX, for the final comparison.
We then proceed to reverse the number. We initialize a variable reversedNum to 0. We repeatedly take the last digit of our current number (x % 10), add it to reversedNum after multiplying reversedNum by 10, and then remove the last digit from x (x / 10).
A critical consideration is potential integer overflow. If the reversed number becomes larger than Integer.MAX_VALUE, it will wrap around and give an incorrect result. To prevent this, we can declare reversedNum as a long.
After the loop finishes (when x becomes 0), we compare reversedNum with originalX. If they are equal, the number is a palindrome.
class Solution { public boolean isPalindrome(int x) { // Negative numbers are not palindromes if (x < 0) { return false; } long reversedNum = 0; int originalX = x; while (x != 0) { int digit = x % 10; reversedNum = reversedNum * 10 + digit; x = x / 10; } return originalX == reversedNum; }}Complexity
Time
O(d), where d is the number of digits in x. We iterate through each digit of the number once.
Space
O(1), as we only use a few variables to store the numbers, regardless of the input size.
Trade-offs
Pros
Solves the problem without using extra space that depends on input size (O(1) space).
Adheres to the 'follow-up' constraint.
Cons
The reversed number can potentially overflow the standard integer type, requiring the use of a larger data type like
longfor the reversed number.
This is the most optimal approach. Instead of reversing the entire number (which risks overflow), we only reverse the second half. We then compare the first half of the original number with the reversed second half. This avoids the overflow problem and is slightly more efficient.
Algorithm
- Handle edge cases: If
xis negative, or ifxends in 0 but is not 0 itself, returnfalse. - Initialize
revertedNumber = 0. - Loop while
x > revertedNumber: a. UpdaterevertedNumber:revertedNumber = revertedNumber * 10 + x % 10. b. Updatex:x = x / 10. - After the loop, compare the first half (
x) with the reversed second half (revertedNumber).- For an even number of digits,
xwill be equal torevertedNumber. - For an odd number of digits, the middle digit will be on
revertedNumber, so we comparexwithrevertedNumber / 10.
- For an even number of digits,
- Return
x == revertedNumber || x == revertedNumber / 10.
Walkthrough
First, we handle some edge cases that can be identified quickly. Negative numbers are not palindromes. Also, any number that ends in 0 (except for 0 itself) cannot be a palindrome (e.g., 10, 120), because a non-zero number cannot start with 0. So, if x < 0 or (x % 10 == 0 && x != 0), we return false.
We initialize a variable revertedNumber = 0. We then enter a loop that continues as long as x is greater than revertedNumber.
Inside the loop, we build up revertedNumber by taking the last digit of x and appending it. Simultaneously, we shrink x by removing its last digit. This process effectively moves digits from the end of x to the end of revertedNumber.
The loop stops when we've processed half of the digits. At this point, x holds the first half of the number, and revertedNumber holds the reversed second half.
Finally, we check for palindrome property:
- If the original number has an even number of digits (e.g., 1221), the loop stops when
xis 12 andrevertedNumberis also 12. So, we check ifx == revertedNumber. - If the original number has an odd number of digits (e.g., 12321), the loop stops when
xis 12 andrevertedNumberis 123. The middle digit '3' is irrelevant for the palindrome check. We can discard it by dividingrevertedNumberby 10. So, we check ifx == revertedNumber / 10. Combining these two conditions, we returntrueifx == revertedNumber || x == revertedNumber / 10.
class Solution { public boolean isPalindrome(int x) { // Edge cases: // 1. Negative numbers are not palindromes. // 2. If the last digit is 0, to be a palindrome, the first digit must also be 0. // Only 0 itself fits this condition. if (x < 0 || (x % 10 == 0 && x != 0)) { return false; } int revertedNumber = 0; while (x > revertedNumber) { revertedNumber = revertedNumber * 10 + x % 10; x /= 10; } // For numbers with an odd number of digits, we can get rid of the middle digit // by revertedNumber/10. For example, when x = 12321, at the end of the while loop // we get x = 12, revertedNumber = 123. // Since the middle digit doesn't matter in a palindrome, we can simply divide it out. return x == revertedNumber || x == revertedNumber / 10; }}Complexity
Time
O(log10(n)) or O(d), where d is the number of digits. More precisely, it's O(d/2) as it only iterates through half the digits.
Space
O(1), as it uses a constant amount of extra space.
Trade-offs
Pros
Most efficient in terms of both time and space.
Avoids the integer overflow problem completely without needing a
long.Processes only half of the digits of the number.
Cons
The logic, especially the final comparison for odd/even length numbers, can be slightly less intuitive at first glance.
Solutions
Solution
public class Solution { public bool IsPalindrome ( int x ) { if ( x < 0 || ( x > 0 && x % 10 == 0 )) { return false ; } int y = 0 ; for (; y < x ; x /= 10 ) { y = y * 10 + x % 10 ; } return x == y || x == y / 10 ; } }class Solution {public boolean isPalindrome(int x) { if (x < 0 || (x > 0 && x % 10 == 0)) { return false; } int y = 0; for (; y < x; x /= 10) { y = y * 10 + x % 10; } return x == y || x == y / 10; }}/** * @param {number} x * @return {boolean} */ var isPalindrome = function (x) { if (x < 0 || (x > 0 && x % 10 === 0)) { return false; } let y = 0; for (; y < x; x = ~~(x / 10)) { y = y * 10 + (x % 10); } return x === y || x === ~~(y / 10);};class Solution {public: bool isPalindrome(int x) { if (x < 0 || (x && x % 10 == 0)) { return false; } int y = 0; for (; y < x; x /= 10) { y = y * 10 + x % 10; } return x == y || x == y / 10; }};class Solution: def isPalindrome(self, x: int) -> bool: if x < 0 or (x and x % 10 == 0): return False y = 0 while y < x: y = y * 10 + x % 10 x //= 10 return x in (y, y // 10)Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.