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.
Plain Text
복사
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.
Plain Text
복사
Example 3:
Input: x = 10
Output: false
Explanation: Reads 01 from right to left. Therefore it is not a palindrome.
Plain Text
복사
Constraints:
•
231 <= x <= 231 - 1
Follow up:
Could you solve it without converting the integer to a string?
At first, I didn't know what a palindrome was, so I looked it up before reading the problem. I found out that a palindrome is a word that reads the same forwards and backwards!
For example, the word "level" reads the same whether you read it from the front or from the back. Other examples of palindromes include "radar," "madam," "racecar," and "noon."
Now that I understand what a palindrome is, let's think about how to solve the problem... Since I'll be solving it in Python, I plan to first convert the numeric input into a string format, then compare the original string with its reversed version, and return the result as a boolean value.
class Solution:
def isPalindrome(self, x: int) -> bool:
x = str(x) # convert Integer type to String
reversed_x = x[::-1] # reversed
if x == reversed_x:
return True
else:
return False
Python
복사
First, the function isPalindrome takes an integer x as its parameter. I then convert the integer x into a string, so the variable x now holds the original number in string format, and the variable reversed_x holds the reversed version of that string.
I then compare the two, and if they match, the function returns True otherwise, it returns False. It's a simple function. Since the difficulty of the problem is labeled as "Easy," the idea came to mind pretty quickly. Now, I'll go ahead and run this code for test cases.
When I ran the code, all three test cases were accepted. Now, let’s go ahead and officially submit the solution.
It passed! However, I noticed that the code I submitted took 8ms to execute. I saw that some other submissions only took 2ms or 4ms, which made me wonder how they wrote their code to achieve such fast execution times.
Review
After looking at other people's submitted solutions, I think I've roughly figured out why my code took as long as 8ms. There seem to be two main reasons.
•
String Conversion – str(x)
The reason why string conversion is slow is because converting an integer to a string is not a simple process. In Python, when you use str(x) to convert an integer to a string, it goes through several internal steps. It's not just copying a value in memory—instead, it interprets the integer as a base-10 number and constructs a string by interpreting and combining each digit as a character. This involves loops, string concatenation, and memory allocation, making it more complex than it seems.
Additionally, strings in Python are immutable, meaning once created, they cannot be changed. Therefore, every time you convert an integer to a string, a new string object is created in memory, which adds overhead from copying and memory management. For example, converting 12345 into a string means generating the characters '1', '2', '3', '4', and '5', and combining them into a new string '12345'.
Even though Python internally applies many optimizations, this process is still heavier and more memory-intensive than simple numerical operations. Especially in algorithm problems where such conversions may occur repeatedly, this accumulated cost can significantly affect execution time.
Thus, in performance-critical situations, it's better to solve problems using integer logic without converting to strings. While string conversion is intuitive and easy to understand, its underlying complexity can be a clear disadvantage in terms of performance.
•
List Slicing – x[::-1]
The main reason slicing is slow is because it creates a new object. Slicing does not simply reference a portion of the original string or list, it actually creates a new copy of the specified range. For instance, x[::-1] reverses the original string and constructs a new string object in memory. Since it must access each character in the original string, the operation takes O(n) time, and it also requires memory allocation for the new object, which adds overhead.
Reverse slicing, in particular, involves negative index stepping, which adds additional computation. Internally, Python must traverse the string in reverse, and this increases the amount of work needed compared to regular slicing.
Furthermore, slicing is often followed by a comparison operation. For example, in x == x[::-1], you have to compare the original string to its reversed copy, character by character,. another O(n) operation. So, slicing and comparing combined require about O(n) + O(n) = O(n) time, but with a significant amount of processing and memory use.
Because of these reasons, platforms like LeetCode tend to favor number-based solutions. They don’t involve string conversion or copying, and instead use mathematical methods to determine if a number is a palindrome, resulting in much faster execution. In short, while slicing is intuitive and concise, it’s not the most efficient method when performance is a priority.
Now that you've identified why your code was slower than others, let's try solving the problem using only numeric operations, without type conversion or list slicing.
Using modulo and division to reverse an integer
class Solution:
def isPalindrome(self, x: int) -> bool:
if x < 0 or (x % 10 == 0 and x != 0):
"""
1. If x is negative, it can't be a palindrome because of the minus sign.
2. If x ends with 0 but is not 0 itself, it can't be a palindrome.
(e.g., 10 reversed is 01, which is not valid in integer form)
"""
return False
reversed_num = 0
while x > reversed_num:
# Append the last digit of x to the reversed number
reversed_num = reversed_num * 10 + x % 10
# Remove the last digit from x
x //= 10
# For even length numbers : x == reversed_num
# For odd length numbers : middle digit doesn't matter, so we do reversed_num // 10
return x == reversed_num or x == reversed_num // 10
Python
복사
Initially, I wrote the code by converting the integer into a string, then reversing it using slicing ([::-1]), and comparing it with the original string to determine whether it was a palindrome. This approach is intuitive and simple to implement, but it comes with performance drawbacks due to unnecessary computations and memory copying involved in string conversion and slicing operations.
To improve this, I shifted to an approach that determines whether the number is a palindrome using only integer operations, without converting it to a string. By extracting the digits from the end of the number one by one and building a reversed version, I can compare it with the original number. This method only processes half of the digits and avoids redundant memory allocation, making it much more efficient. As a result, the solution has been significantly optimized for better performance compared to the initial version.
Example of Using modulo and division to reverse an integer - x = 1234
Step | x | x % 10 (last digit) | reversed_num | Explanation |
1 | 1234 | 4 | 0 → 0*10+4 = 4 | Place 4 at the start of the new number |
2 | 123 | 3 | 4 → 4*10+3 = 43 | Append 3 in front |
3 | 12 | 2 | 43 → 43*10+2 = 432 | Append 2 in front |
4 | 1 | 1 | 432 → 432*10+1 = 4321 | Append 1 in front |
5 | 0 | End | 4321 | Reversal complete |