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 - 1Follow up: Could you solve it without converting the integer to a string?
Problem Overview: Given an integer x, determine whether it reads the same forward and backward. A number like 121 is a palindrome, while 123 is not. Negative numbers are automatically invalid because the minus sign only appears on the left side.
Approach 1: String Conversion Method (O(d) time, O(d) space)
The most straightforward approach converts the integer to a string and checks if the string reads the same from both directions. After converting x to str(x), use two pointers or simply compare the string with its reversed version. The algorithm iterates from both ends toward the center, comparing characters at each position. If every pair matches, the number is a palindrome.
This method works well because string operations are simple and readable. The time complexity is O(d), where d is the number of digits, since each digit is examined at most once. The downside is the additional memory used for the string representation, giving O(d) space complexity. Even with that overhead, this approach is perfectly acceptable for most interview scenarios involving math problems.
Approach 2: Reversing Half of the Number (O(log n) time, O(1) space)
A more optimal approach avoids converting the number to a string. Instead, reverse only half of the digits using pure arithmetic. Repeatedly extract the last digit with x % 10 and append it to a reversed value using rev = rev * 10 + digit. Stop when the reversed half becomes greater than or equal to the remaining half of the original number.
The key insight is that a palindrome mirrors around its center. Once half the digits are reversed, you only need to compare the two halves. For even-digit numbers, check x == rev. For odd-digit numbers, ignore the middle digit using x == rev / 10. This avoids reversing the entire integer and prevents overflow issues.
This algorithm runs in O(log n) time because each iteration removes one digit from the number. Space complexity is O(1) since it only uses a few integer variables. The technique relies purely on integer manipulation, making it a good demonstration of math reasoning and two-pointer style symmetry thinking applied to digits.
Recommended for interviews: Start by explaining the string approach since it demonstrates the core palindrome idea quickly. Then move to the reverse-half technique, which interviewers usually expect for optimal performance. Showing both methods proves you understand the problem conceptually and can optimize it using numeric operations.
In this method, we convert the integer to a string and check if it reads the same forwards and backwards. This approach is straightforward and leverages the built-in string operations.
The function checks if the integer is negative, returning false immediately if so, as negative numbers can't be palindromes. We convert the integer into a string and use a loop to compare characters from the start and end of the string. If they match all the way to the middle, the number is a palindrome.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n), where n is the length of the string representation of the number.
Space Complexity: O(n) for the string conversion.
This approach avoids the use of string conversions by reversing half of the digits of the number and comparing the two halves. This is more memory efficient as it only creates a few integer variables.
The function checks if the number is negative or ends with a zero (and is not zero itself), returning false in those cases. It then sequentially takes digits from the end of the number, constructing a reversed half. The loop terminates once reversedHalf equals or exceeds the original half of the number, allowing us to check equality.
C++
Java
Python
C#
JavaScript
Time Complexity: O(log10(n)), where n is the input number because we are dividing the number by 10 in each iteration.
Space Complexity: O(1) because no additional space proportional to input size is used.
| Approach | Complexity |
|---|---|
| String Conversion Method | Time Complexity: O(n), where n is the length of the string representation of the number. |
| Reversing Half of the Number | Time Complexity: O(log10(n)), where n is the input number because we are dividing the number by 10 in each iteration. |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| String Conversion Method | O(d) | O(d) | Simple implementation when extra memory is acceptable |
| Reverse Half of the Number | O(log n) | O(1) | Optimal solution for interviews or memory‑constrained environments |
Longest Palindromic Substring - Python - Leetcode 5 • NeetCode • 629,070 views views
Watch 9 more video solutions →Practice Palindrome Number with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor