Palindrome Number

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:

• -2^31 <= x <= 2^31 - 1

My Solution

Right off, we know that if the number is negative, it can never be a palindrome, so we can return false right away if the number is negative.

If it’s positive, we can extract the digits of the number and then use the two pointer technique to check that digits at symmetrical positions in the number are the same. If they are, it’s a palindrome. If not, it isn’t.

The algorithmic time complexity would be O(digits(x)) in the first pass to extract the digits and then also in the second pass to check for symmetry using the two pointer technique. The algorithmic space complexity is also O(digits(x)) to store the extracted digits.

class Solution {
    public boolean isPalindrome(int x) {
        if (x < 0) {
            return false;
        }

        List<Integer> digits = new ArrayList<>();

        while (x > 0) {
            digits.add(x % 10);
            x /= 10;
        }

        int i = 0;
        int j = digits.size()-1;
        while (i < j) {
            if (digits.get(i) != digits.get(j)) {
                return false;
            }
            i++;
            j--;
        }

        return true;
    }
}