9. Palindrome Number - Explanation

Description

You are given an integer x, return true if x is a palindrome, and false otherwise.

Note: An integer is a palindrome when it reads the same forward and backward.

For example, 111 and 121 are palindromes while 123 is not.

Example 1:

Input: x = 1

Output: true

Example 2:

Input: x = -1

Output: false

Constraints:

-(2^31) <= x <= ((2^31) - 1)

Follow up: Could you solve it without converting the integer to a string?

Company Tags

Please upgrade to NeetCode Pro to view company tags.

1. Convert to String

Intuition

The most straightforward approach is to convert the integer to a string and check if the string is a palindrome by reversing it.

If the original string equals its reversed version, the number is a palindrome.

Algorithm

Convert the integer to its string representation.
Reverse the string.
Compare the original string with the reversed string.
Return true if they are equal, false otherwise.

class Solution:
    def isPalindrome(self, x: int) -> bool:
        s = str(x)
        return s == s[::-1]

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(n)$

Where $n$ is the number of digits in the given integer.

2. Convert to String (Optimal)

Intuition

Instead of creating a reversed copy of the entire string, we can compare characters from both ends moving toward the center. This avoids the extra space needed for the reversed string.

We only need to check half the string since we compare characters in pairs.

Algorithm

Convert the integer to its string representation.
Initialize two pointers: i at the start and j at the end.
While i < n/2, compare s[i] with s[n - i - 1]. If they differ, return false.
Return true if all comparisons pass.

class Solution:
    def isPalindrome(self, x: int) -> bool:
        s = str(x)
        n = len(s)
        for i in range(n // 2):
            if s[i] != s[n - i - 1]:
                return False
        return True

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(n)$

Where $n$ is the number of digits in the given integer.

3. Reverse the Integer

Intuition

Without using string conversion, we can reverse the entire integer mathematically and compare it to the original. If they are equal, the number is a palindrome.

Negative numbers cannot be palindromes because of the negative sign. We build the reversed number digit by digit using modulo and division operations.

Algorithm

If the number is negative, return false immediately.
Initialize rev = 0 and num = x.
While num > 0:
- Extract the last digit using num % 10.
- Append it to rev by computing rev = rev * 10 + digit.
- Remove the last digit from num using integer division.
Compare rev with the original x and return true if equal.

class Solution:
    def isPalindrome(self, x: int) -> bool:
        if x < 0:
            return False

        rev = 0
        num = x
        while num:
            rev = (rev * 10) + (num % 10)
            num //= 10

        return rev == x

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(1)$

Where $n$ is the number of digits in the given integer.

4. Two Pointers

Intuition

We can compare digits from both ends without converting to a string or reversing the entire number. The idea is to extract the leftmost and rightmost digits and compare them.

We use a divisor to extract the leftmost digit and modulo to extract the rightmost digit, then shrink the number from both ends.

Algorithm

If the number is negative, return false.
Find the divisor div such that x / div gives the first digit. This is the largest power of 10 less than or equal to x.
While x > 0:
- Compare the first digit (x / div) with the last digit (x % 10). If they differ, return false.
- Remove both the first and last digits: x = (x % div) / 10.
- Update the divisor: div /= 100 (since we removed two digits).
Return true if all comparisons pass.

class Solution:
    def isPalindrome(self, x: int) -> bool:
        if x < 0:
            return False

        div = 1
        while x >= 10 * div:
            div *= 10

        while x:
            if x // div != x % 10:
                return False
            x = (x % div) // 10
            div //= 100

        return True

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(1)$

Where $n$ is the number of digits in the given integer.

5. Reverse Half of the Number

Intuition

Reversing the entire number risks integer overflow. A clever optimization is to reverse only the second half of the number and compare it to the first half.

We keep extracting digits from the end and building the reversed half until the reversed half is greater than or equal to the remaining number. At that point, we have processed half (or just past half) of the digits.

Algorithm

Handle edge cases: negative numbers and numbers ending in 0 (except 0 itself) are not palindromes.
Initialize rev = 0.
While x > rev:
- Extract the last digit of x and append it to rev.
- Remove the last digit from x.
After the loop, compare x == rev (even length) or x == rev / 10 (odd length, where the middle digit is in rev).
Return true if either condition holds.

class Solution:
    def isPalindrome(self, x: int) -> bool:
        if x < 0 or (x != 0 and x % 10 == 0):
            return False

        rev = 0
        while x > rev:
            rev = (rev * 10) + (x % 10)
            x //= 10

        return x == rev or x == rev // 10

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(1)$

Where $n$ is the number of digits in the given integer.

Common Pitfalls

Forgetting Negative Numbers Are Not Palindromes

Negative numbers have a minus sign at the front, so they can never be palindromes (e.g., -121 reads as 121- backwards). Failing to handle negative numbers as an early return case leads to incorrect results or issues with modulo operations on negative values.

Not Handling Numbers Ending in Zero

Numbers ending in zero (except zero itself) cannot be palindromes because leading zeros are not allowed in integers. For example, 10 would need to be 01 reversed, which is not a valid representation. The half-reversal approach fails on these cases without explicit handling, as the loop condition x > rev may never be satisfied correctly.