9. Palindrome Number - Detailed Explanation

Free Coding Questions Catalog

Boost your coding skills with our essential coding questions catalog. Take a step towards a better tech career now!

Problem Statement

LeetCode 9. Palindrome Number: Given an integer x, determine whether x is a palindrome. An integer is a palindrome when it reads the same backward as forward.

For example, 121 is a palindrome because it reads as 121 from left to right and also 121 from right to left.
In contrast, 123 is not a palindrome because reading it backward gives 321, which is not the same as 123.

If x is negative or if it ends in 0 (but is not zero itself), then it cannot be a palindrome. Negative numbers have a minus sign that doesn't read the same backward (e.g. -121 becomes 121- backward, which is not the same). Similarly, a positive number ending in 0 (like 10) will have a leading 0 when reversed (01), which doesn’t match the original form.

Examples:

Input: x = 121
Output: true
Explanation: 121 reads the same forward and backward, so it’s a palindrome.
Input: x = -121
Output: false
Explanation: From left to right, it is "-121". From right to left, it becomes "121-", which is not the same. Negative numbers are not palindromic due to the - sign.
Input: x = 10
Output: false
Explanation: Right to left it reads "01", which is not the same as "10". So 10 is not a palindrome.

Constraints: -2^31 <= x <= 2^31 - 1 (i.e., x fits in a 32-bit signed integer range) . This means x can have up to 10 digits in magnitude. We should consider time and space efficiency, and note that reversing a large 10-digit number could overflow a 32-bit int in some languages (like Java/C++) if not handled carefully.

Hints

Hint 1: Think of how you would check if a string is a palindrome. You might compare characters from the start and end moving toward the center, or simply reverse the string and compare it to the original. Can you apply a similar idea to the digits of an integer?
Hint 2: How can you get the last digit of an integer? (Think about the modulus operator %.) How can you remove the last digit? (Think about integer division // or /.) These operations can help peel off digits from the number.
Hint 3: What are some cases that can immediately be ruled out? For example, any negative number is not a palindrome (due to the - sign). Also, any positive number ending in 0 (like 10, 20, 100) cannot be a palindrome unless the number is 0 itself.
Hint 4: Instead of reversing the entire number (which could risk overflow and unnecessary work), consider if you can reverse half of the number and then compare it with the remaining half. This can avoid overflow and improve efficiency.
Hint 5: If you’re thinking recursively, consider how you might compare the first and last digits and then reduce the problem (for example, by stripping those digits and checking the smaller number in the middle).

Using these hints, try to formulate an approach before looking at the solutions below!

Multiple Approaches

We will discuss several approaches to determine if an integer is a palindrome. We start from a simple brute-force solution and then improve upon it step by step. For each approach, we provide an explanation, Python and Java implementation, and analyze time and space complexity.

Approach 1: Brute Force – Convert to String and Check Palindrome

Idea: The simplest way to check if a number is a palindrome is to convert it to a string and check if the string reads the same backward as forward. If the string is equal to its reverse, then the number is a palindrome. This is straightforward and easy to implement, though it uses extra space for the string.

Steps:

If x is negative, immediately return False (negative numbers are not palindromic due to the minus sign).
Convert the number to a string, e.g., "121" for 121.
Reverse the string (in Python you can do s[::-1], in Java you might use new StringBuilder(s).reverse()).
Compare the original string with the reversed string. If they are the same, return True; otherwise, return False.

This approach essentially treats the problem as a palindrome-check on a string.

Python Implementation (Approach 1):

Python3

. . . .

Java Implementation (Approach 1):

Java

. . . .

Complexity: Let n be the number of digits in x. Converting to a string and reversing it takes O(n) time. Comparing two strings of length n is also O(n) in the worst case, so the time complexity is O(n). Space complexity is O(n) as we create a copy of the number in string form and another for the reversed string. Here n is at most 10 for a 32-bit integer, so this is very efficient in practice. However, some interviews may ask you to solve it without using extra space for the string (see the follow-up in the problem).

Note: This approach is very straightforward, but it uses extra memory for the string. It's a good initial solution for clarity, but we will explore in-place numerical methods next (as hinted by the follow-up question asking to avoid string conversion).

Approach 2: Iterative Two-Pointer (Compare First and Last Digits)

Idea: We can check the palindrome property by comparing digits from the outside-in, similar to how we'd compare characters in a string using two pointers (one at the start and one at the end). For an integer, we can extract the first and last digits and compare them, then peel those digits off and continue with the next pair.

How to get first and last digits? If the number has d digits, the last digit is x % 10. The first digit can be found by using division by 10^{d-1}. For example, for x = 12321, the first digit can be obtained by dividing by 10000 (10^(5-1)) to get 1, and the last digit is 12321 % 10 = 1.

We can find the divisor div as the largest power of 10 less than or equal to x. One way is to start div = 1 and multiply by 10 until x/div < 10 (meaning div is just below the number of digits). For 12321, this loop gives div = 10000. Then:

Compare the leading digit x // div and trailing digit x % 10. If they differ, it's not a palindrome.
If they are the same, remove those digits from x. You can remove the trailing digit by doing integer division by 10 (x = x // 10). Removing the leading digit is trickier; one way is to take the remainder of x by div to drop the leading digit, then again do integer division by 10 to drop the trailing digit. In code: x = (x % div) // 10 . This effectively drops the first and last digits of x.
After removing two digits, reduce div by a factor of 100 (since the number now has two fewer digits) and continue the comparisons.

Continue this process until the number has no digits left or only one digit (which would mean all pairs matched).

Steps:

If x < 0, return False (no negative palindromes). If x is 0, return True (0 is a palindrome by definition).
Compute div as the highest power of 10 <= x. For example, if x=12321, div becomes 10000.
While x != 0:
a. Let leading = x // div (first digit) and trailing = x % 10 (last digit).
b. If leading != trailing, return False (mismatch found).
c. Remove the leading and trailing digits: x = (x % div) // 10.
d. Reduce div by 100 (because we removed two digits).
If the loop finishes without mismatches, return True.

Python Implementation (Approach 2):

Python3

. . . .

Java Implementation (Approach 2):

Java

. . . .

Complexity: Let n be the number of digits. In the worst case, we compare and remove two digits in each iteration. So roughly n/2 iterations are needed, making time complexity O(n). Finding the initial divisor also takes O(n) in the number of digits. Space complexity is O(1) since we are only using a few integer variables. This approach does not create new strings or use extra arrays, it operates on the number in-place.

Discussion: This approach avoids converting to a string and uses a two-pointer technique on the number itself. It’s efficient and uses constant space. However, be careful with integer math (especially in other languages) to avoid overflow when computing the divisor (though in our case, div will at most be 10^9 which is safe for 32-bit int). Also, this approach inherently handles the even and odd length cases correctly by eventually reducing x to 0 or a single digit.

Approach 3: Recursive Approach

Idea: We can also solve the problem using recursion. The idea here can be implemented in two ways:

Recursively compare first and last digits (similar to Approach 2 but using recursion).
Or recursively reverse the number (building the reversed number via recursive calls) and then compare with the original.

For simplicity, we'll demonstrate the second idea: recursively constructing the reverse of the number. The recursion will peel off the last digit of the number in each call and build the reversed number as we unwind the recursion.

Steps (recursive reversal):

If x < 0, return False (negative not palindrome).
Use a helper recursive function that takes two parameters: the remaining part of the number n and the current reversed value built so far. For example, helper(n, rev_so_far).
The helper will extract the last digit of n and add it to rev_so_far. Then it will recurse with the smaller number (with last digit removed) and the new rev_so_far.
Base case: when n becomes 0 (we've processed all digits), return the final rev_so_far.
Compare the resulting reversed number with the original. If they are equal, it's a palindrome.

Alternatively, one can write the recursion to directly return a boolean by comparing first and last digits at each step, but that requires a way to drop the first and last digits in each recursive call (similar logic as approach 2).

Python Implementation (Approach 3):

Python3

. . . .

In this Python code, the helper function builds the reversed number rev by recursion (similar to how you'd build it in a loop). For example, if x = 123, the recursion would do:

helper(123, 0) calls helper(12, 3) (rev becomes 3)
which calls helper(1, 32) (rev becomes 32)
which calls helper(0, 321) (rev becomes 321 and returns)
Then we compare 321 with the original 123.

Java Implementation (Approach 3):

Java

. . . .

In the Java implementation, reverseHelper(n, rev) accumulates the reversed number in rev. We call reverseHelper(x, 0) and then check if the result equals the original x.

Complexity: The recursive approach also processes each digit once, so it is O(n) time for n digits. Space complexity is O(n) stack space due to recursion (each recursive call adds a layer to the call stack). For a maximum 10-digit number, this is at most 10 recursive calls, which is fine. However, it's generally good to be cautious with recursion for very large inputs to avoid stack overflow. In this problem, iteration is just as straightforward, so recursion is mostly for demonstration.

Discussion: This approach essentially mirrors the full number reversal logic (like Approach 1 or 2) but implements it recursively. Another possible recursive strategy is to compare first and last digits recursively; however, that approach is a bit more complex to implement (you'd need to pass around or compute the appropriate divisor/power of 10 at each step). The provided recursive solution highlights how you can build the reversed number in a recursive manner. In interviews, an iterative solution is typically preferred for this problem, but it's good to know multiple ways to think about it.

Approach 4: Optimal Mathematical Approach (Reversing Half of the Number)

Idea: This is a more optimal solution that avoids reversing the entire number, thereby reducing the risk of overflow and unnecessary work. The key insight is that we only need to reverse half of the digits of the number and compare it with the other half.

How does this work? Imagine we push the digits from the end of the number onto a new number (as in the full reversal) but stop when the reversed part becomes greater than or equal to the remaining part of the original. At that point, we have reversed half the digits. For a palindrome:

If the number of digits is even, the reversed half will exactly equal the remaining half.
If the number of digits is odd, the reversed half will be equal to the remaining half when we drop the middle digit (because the middle digit doesn't need to match anything but itself).

Special cases: If x < 0, return false (as before). If x ends in 0 (and x is not 0), return false. Why? Because if a number ends in 0 and is a palindrome, it would have to start with 0 – the only number that fits that description is 0 itself. For example, 10 is not a palindrome (ends with 0 but doesn't start with 0).

Steps:

If x < 0 or (x % 10 == 0 and x != 0), return False immediately (negative or ends in 0 but not 0).
Initialize reverted (the reversed half) to 0.
While x > reverted:
a. Take the last digit of x (i.e., x % 10) and append it to reverted (i.e., reverted = reverted * 10 + (x % 10)).
b. Remove the last digit from x (x //= 10).
We loop until reverted is no longer less than x – this means we've processed at least half the digits .
After the loop, x holds the first half of the number (for odd length, it will be slightly larger than the first half) and reverted holds the reversed second half of the number.
Check if x == reverted (even-length case) or x == reverted // 10 (odd-length case, we drop the middle digit from reverted) . If either condition is true, return True; otherwise, return False.

For example, consider x = 12321:

Initial: x = 12321, reverted = 0.
Iteration 1: take last digit 1 -> reverted = 1, x = 1232.
Iteration 2: take last digit 2 -> reverted = 12, x = 123.
Iteration 3: take last digit 3 -> reverted = 123, x = 12. Now reverted (123) is greater than x (12), so stop.
Now x = 12 and reverted = 123. We drop the middle digit of the original by doing reverted // 10, which gives 12. Now x == 12 and reverted//10 == 12, so they match, confirming it’s a palindrome.

This method effectively reversed only half of the number’s digits.

Python Implementation (Approach 4):

Python3

. . . .

Java Implementation (Approach 4):

Java

. . . .

Complexity: The loop runs at most half the length of the number’s digits, so roughly O(n/2) which simplifies to O(n) time where n is the number of digits. In terms of the actual input value, each loop iteration divides the number by 10, so it’s O(log_{10}(x)) time. Space complexity is O(1) since we use only a couple of integer variables.

Why this is optimal: We avoid reversing the entire number (which could overflow a 32-bit integer if we didn’t use a larger type) by stopping at half. We also avoid using extra space like a string or array. This is the approach recommended by the official LeetCode solution: it handles all cases efficiently and safely.

Complexity Analysis (Summary)

Brute Force (String) Approach: Time O(n), Space O(n), where n is the number of digits. We iterate over the string representation and use extra space equal to its length.
Iterative Two-Pointer Approach: Time O(n), Space O(1). We compare digits from both ends, using arithmetic operations. We touch each digit at most once.
Recursive Approach: Time O(n), Space O(n) due to recursion stack. The operations are similar to the iterative reversal, but the recursion adds linear stack depth.
Optimal Half-Reverse Approach: Time O(n) (actually O(n/2) which is O(n)), Space O(1). We reverse half of the digits. This is the most efficient in terms of space and avoids potential overflow issues.

Note: Here n refers to the number of digits in the integer. In terms of the value of x, the time complexity is O(log_{10}(x)) since the number of digits is proportional to the logarithm of the number’s value. All approaches have linear complexity in the number of digits, which for a fixed maximum of 10 (in 32-bit int) is constant, but we analyze it in Big-O terms for general understanding.

Step-by-Step Example Walkthrough

Let’s walk through a concrete example to visualize how the palindrome check works. We’ll use the number x = 12321 (which is a palindrome) and demonstrate the process of the iterative reversal approach (Approach 2 or full reversal logic). The same steps apply conceptually to the other approaches with slight differences in when they stop.

Figure: Flowchart of an algorithm to check if a number is a palindrome by reversing the number and comparing with the original. The process reads the number's digits in reverse order to form the reversed number, then compares it to the original.

Let's follow the steps for x = 12321:

Initial State: original = 12321, reverse = 0. (We also note original for final comparison.)
Iteration 1: Extract the last digit: digit = original % 10 = 12321 % 10 = 1. Append this digit to reverse: reverse = 0 * 10 + 1 = 1. Remove the last digit from original: original = original // 10 = 12321 // 10 = 1232.
State now: original = 1232, reverse = 1.
Iteration 2: Last digit of original is 2. Do reverse = 1 * 10 + 2 = 12. Update original = 1232 // 10 = 123.
State now: original = 123, reverse = 12.
Iteration 3: Last digit is 3. Do reverse = 12 * 10 + 3 = 123. Update original = 123 // 10 = 12.
State now: original = 12, reverse = 123.
Iteration 4: Last digit is 2. Do reverse = 123 * 10 + 2 = 1232. Update original = 12 // 10 = 1.
State now: original = 1, reverse = 1232.
Iteration 5: Last digit is 1. Do reverse = 1232 * 10 + 1 = 12321. Update original = 1 // 10 = 0.
State now: original = 0, reverse = 12321.
End: original has become 0, and reverse = 12321. Now we compare the reverse with the initial number. Since 12321 (reversed) equals 12321 (initial), the result is True – the number is a palindrome.

In the optimal half-reverse approach, the process would stop around step 3 when reverse (123) became greater than the remaining original (12), and then a comparison would confirm the palindrome. But as you can see, the core idea is building the reversed number and comparing.

For a non-palindrome example, say x = 123, the process would yield reverse = 321 and original would be 0, then comparing 321 to 123 would show a mismatch (not a palindrome). In the two-pointer approach, a mismatch would be caught earlier (comparing first and last digit 1 vs 3).

This step-by-step simulation helps verify the logic and shows why the methods work.

Common Mistakes and Edge Cases

Negative Numbers: Remember that by definition, negative numbers are not palindromic (the reversed sequence includes the minus sign at the end, which is not equal to the original format). A common mistake is to think -121 might be considered palindrome if you ignore the sign. In this problem, simply return false for any negative input.
Numbers Ending in Zero: Any positive number ending in 0 (like 10, 120, 590) cannot be a palindrome unless the number is actually 0. If the last digit is 0 but the number isn’t 0, the first digit of the number won’t be 0, so it fails the palindrome test. For example, 10 is not a palindrome (01 ≠ 10). Many optimal solutions explicitly check for this case.
Single Digit Numbers: All single-digit numbers (0 through 9) are palindromes. Make sure your logic returns true for single digit inputs. This is an easy case to handle, but don’t accidentally exclude it with an overly strict check. In our approaches, single digits naturally work (the string method handles it, the iterative comparison will immediately return true or fall out of the loop, etc.).
Overflow (in some languages): If you choose to reverse the entire number using arithmetic in a language like Java or C++, be mindful of potential overflow. For instance, reversing 2147483647 (which is 2^31-1, the largest 32-bit int) would produce 7463847412, which is beyond the 32-bit range. Our Approach 2 (full reversal) would overflow a 32-bit int. To avoid this, one could use a larger data type (like long in Java ) or use the half-reversal method which inherently avoids creating a number larger than the original. In Python, integers can grow arbitrarily large so overflow isn’t an issue, but it’s something to consider in lower-level languages.
Leading Zeros in Reversed: If using the string approach or full reverse, the reversed number/string may have leading zeros in theory (e.g., 100 -> "001"). However, when comparing, "001" as a string is not equal to "100", and numerically 001 is just 1 which won’t equal 100. The logic of our solutions already accounts for this by the nature of how comparisons work, but it’s good to be aware. The two-pointer method explicitly handles this by removing both first and last digits together.
Recursion Pitfalls: If implementing a recursive solution, ensure you handle the base case correctly. Also, be cautious of using recursion for very large inputs. Although in this problem the input size (number of digits) is limited, forgetting a base case or not reducing the problem size correctly can cause infinite recursion or stack overflow.
Ignoring the Follow-up: In an interview or competitive setting, after giving a string-based solution, you might be asked to solve it without converting to a string (as noted in the problem statement). A common mistake is not attempting the in-place numeric solution when prompted. Make sure to practice the numeric approaches (like the ones described above), as they show a deeper understanding of the problem.

By keeping these points in mind, you can avoid the common pitfalls associated with this problem. Always test your solution with edge cases: negative numbers, 0, numbers like 1, 7 (single digits), numbers ending in 0 (10, 100, 1000), and a large palindrome vs. a large non-palindrome.

Checking for palindromes is a common theme. Here are some related problems and variations you can practice:

Palindrome Linked List (LeetCode 234): Determine if a linked list is a palindrome. This is conceptually similar to this problem, but you need to do it with the values of nodes in a linked list. Techniques involve finding the middle of the list and reversing the second half (very akin to our optimal approach) or using a stack/recursion.
Valid Palindrome (LeetCode 125): Check if a given string is a palindrome, considering only alphanumeric characters and ignoring cases. This is a string manipulation problem that can be solved with two-pointer technique.
Largest Palindrome Product (LeetCode 479 / Project Euler 4): Find the largest palindrome made from the product of two n-digit numbers. This is a more advanced problem that involves generating palindromes or iterating through combinations of factors.
Closest Palindrome Number (LeetCode 564): Given a number, find the nearest palindrome number (either smaller or larger). This is a challenging problem that involves understanding how palindromes are formed and trying out modifications of the original number.
Palindrome Partitioning (LeetCode 131, 132): These problems involve partitioning a string into substrings that are palindromes (more complex, uses backtracking or dynamic programming).
Strictly Palindromic Number (LeetCode 2396): A trick problem about palindromes in different bases.

9. Palindrome Number - Detailed Explanation

Problem Statement

Hints

Multiple Approaches

Approach 1: Brute Force – Convert to String and Check Palindrome

Approach 2: Iterative Two-Pointer (Compare First and Last Digits)

Approach 3: Recursive Approach

Approach 4: Optimal Mathematical Approach (Reversing Half of the Number)

Complexity Analysis (Summary)

Step-by-Step Example Walkthrough

Common Mistakes and Edge Cases

Related Problems and Variations