Palindrome Number - Leetcode 9 - Python
Palindrome Number - Video Solution
Watch 10 video solutions for Palindrome Number, a easy level problem involving Math. This walkthrough by NeetCode has 117,836 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
Problem Statement
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?
Approach Overview
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. The catch: negative numbers and numbers ending in 0 (except 0 itself) cannot be palindromes.
Approach 1: String Conversion Method (Time: O(d), Space: O(d))
Convert the integer into a string and compare characters from both ends. You can either reverse the string and check equality with the original, or use two pointers starting at the first and last character and move them inward while comparing digits. The key insight is that palindrome validation becomes a simple symmetric comparison problem once the number is represented as text. This approach is straightforward and easy to implement in languages with strong string utilities. The tradeoff is extra memory for the string representation.
This method relies on basic operations from math and simple character comparisons. It’s often the fastest way to write a correct solution during early practice or when code clarity matters more than strict memory optimization.
Approach 2: Reversing Half of the Number (Time: O(log n), Space: O(1))
This approach avoids string conversion and works purely with integer arithmetic. Repeatedly extract the last digit using x % 10 and build a reversed value using reversed = reversed * 10 + digit. Instead of reversing the entire number, stop when the reversed half becomes greater than or equal to the remaining half. At that point you’ve processed half the digits.
The key insight: a palindrome mirrors around its center. If the reversed second half equals the remaining first half, the number is a palindrome. For numbers with an odd number of digits, discard the middle digit by dividing the reversed half by 10. This avoids overflow and reduces unnecessary work.
This technique is a classic math-based digit manipulation problem. Conceptually it resembles a two‑pointer comparison, but performed numerically instead of on an array or string.
Recommended for interviews: Reversing half of the number. Interviewers prefer it because it demonstrates control over digit extraction, edge case handling, and constant-space reasoning. The string approach shows you understand the core palindrome concept, but the half-reversal method shows stronger algorithmic thinking and attention to constraints.
Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| String Conversion Method | O(d) | O(d) | When simplicity and readability matter more than memory usage |
| Reverse Half of the Number | O(log n) | O(1) | Preferred interview solution; avoids string conversion and uses constant space |