Palindrome Number Leetcode Problem - 5 Solutions in Java: Naive, Intermediate, Optimal, and More

When working with numbers in programming, one of the interesting problems that often comes up is checking if a number is a palindrome. A palindrome number is a number that reads the same backward as forward, like 121, 1331, or 909. In this article, we’ll explore the “Palindrome Number” leetcode problem in Java, diving into detailed explanations of the problem and providing solutions at various levels of complexity, from naive to optimal approaches, and even including other interesting solutions you may encounter. The focus will be on helping developers understand the nuances of different methods in Java.

What is a Palindrome Number?

A palindrome number is a number that remains the same when its digits are reversed. For example:

121 is a palindrome because reversing the digits gives us the same number, 121.
909 is also a palindrome because reversing it still results in 909.
123 is not a palindrome because the reverse is 321, which is different from 123.

Leetcode Problem: Palindrome Number

Why Is the Palindrome Number Problem Important in Java?

The palindrome number problem is a fundamental problem that helps in understanding various concepts such as loops, conditionals, and number manipulation in Java. It’s a good practice problem for beginners, intermediate coders, and even for optimization and efficiency-focused solutions.

In this article, we’ll focus on multiple solutions to the Palindrome Number Leetcode Java problem:

The Naive Solution using string manipulation.
An Intermediate Solution using mathematical operations.
The Optimal Solution that reduces the time complexity by reversing only half of the number.
An Iterative Solution using stacks for a different perspective.
An Alternative Approach using a queue (less common, but insightful).

Also check: Recursive Algorithm/ Recursion Algorithm Explained with Examples

Naive Approach for Palindrome Number: Using String Manipulation

Let’s start with the naive approach. In this approach, we can convert the number into a string, reverse it, and check if it is equal to the original number. This is an easy solution but not efficient, especially for very large numbers, because it involves extra space for storing the string.

Naive Palindrome Number Java Leetcode Solution

public class PalindromeNumber {

    public static boolean isPalindrome(int num) {
        // Convert the number to a string
        String original = String.valueOf(num);
        
        // Reverse the string
        String reversed = new StringBuilder(original).reverse().toString();
        
        // Check if the original string is equal to the reversed string
        return original.equals(reversed);
    }

    public static void main(String[] args) {
        int num1 = 121;
        int num2 = -121;
        int num3 = 123;
        
        System.out.println(isPalindrome(num1)); // true
        System.out.println(isPalindrome(num2)); // false
        System.out.println(isPalindrome(num3)); // false
    }
}

Explanation:

String.valueOf(num): Converts the number into a string representation.
new StringBuilder(original).reverse(): Uses the StringBuilder class to reverse the string.
equals(): Compares the original string with the reversed string.

Time Complexity:

The time complexity is O(n), where n is the number of digits in the number.
The space complexity is O(n) due to string manipulation.

Intermediate Approach for Palindrome Number: Using Mathematical Operations

The intermediate approach for checking whether a number is a palindrome avoids converting the number to a string. Instead, it uses mathematical operations to reverse the number and compare it with the original number. This approach is more efficient than the naive solution in terms of space complexity.

Intermediate Palindrome Number Java Leetcode Solution

public class PalindromeNumber {

    public static boolean isPalindrome(int num) {
        // Negative numbers are not palindrome numbers
        if (num < 0) return false;

        // Store the original number to compare later
        int original = num;
        int reversed = 0;

        while (num != 0) {
            // Extract the last digit of the number
            int lastDigit = num % 10;

            // Build the reversed number
            reversed = reversed * 10 + lastDigit;

            // Remove the last digit from the original number
            num /= 10;
        }

        // Compare the reversed number with the original number
        return original == reversed;
    }

    public static void main(String[] args) {
        int num1 = 121;
        int num2 = -121;
        int num3 = 123;

        System.out.println(isPalindrome(num1)); // true
        System.out.println(isPalindrome(num2)); // false
        System.out.println(isPalindrome(num3)); // false
    }
}

Explanation:

The number is reversed using mathematical operations (modulus and division).
We check if the reversed number is equal to the original number.

Time Complexity:

The time complexity is O(n), where n is the number of digits in the number.
The space complexity is O(1) because only a few integer variables are used.

Optimal Approach for Palindrome Number: Reversing Half the Number

The optimal solution reduces the time complexity further by reversing only half of the number. This is especially useful when working with very large numbers.

Optimal Palindrome Number Java Leetcode Solution

public class PalindromeNumber {

    public static boolean isPalindrome(int num) {
        // Negative numbers and numbers ending in 0 (except 0 itself) are not palindromes
        if (num < 0 || (num % 10 == 0 && num != 0)) {
            return false;
        }

        int reversedHalf = 0;
        while (num > reversedHalf) {
            int lastDigit = num % 10;
            reversedHalf = reversedHalf * 10 + lastDigit;
            num /= 10;
        }

        // If the number has an odd number of digits, we ignore the middle digit
        return num == reversedHalf || num == reversedHalf / 10;
    }

    public static void main(String[] args) {
        int num1 = 121;
        int num2 = -121;
        int num3 = 123;

        System.out.println(isPalindrome(num1)); // true
        System.out.println(isPalindrome(num2)); // false
        System.out.println(isPalindrome(num3)); // false
    }
}

Explanation:

Negative numbers and numbers ending in 0 are ruled out immediately.
The number is reversed halfway until we have processed half of its digits.
For odd-length numbers, the middle digit is ignored in comparison.

Time Complexity:

The time complexity is O(log n) because we only reverse half of the digits.
The space complexity is O(1) due to the constant space used.

Also check: Master Binary Search Recursive & Binary Search Iterative – 5 Leetcode Java Solutions

Additional Palindrome Number Solutions: Stacks and Queues

For developers who like to explore different perspectives, we can use stacks or queues to solve the palindrome problem. While less common, these data structures can still provide valuable insights into problem-solving approaches.

Palindrome Number Java Leetcode Solution Using Stack

Using a stack can help us reverse the digits of a number, and then we can compare them with the original digits.

import java.util.Stack;

public class PalindromeNumber {

    public static boolean isPalindrome(int num) {
        if (num < 0) return false; // Negative numbers are not palindromes
        
        Stack<Integer> stack = new Stack<>();
        int original = num;
        
        // Push digits onto the stack
        while (num > 0) {
            stack.push(num % 10);
            num /= 10;
        }

        // Compare the digits from the stack with the original number
        while (original > 0) {
            if (stack.pop() != original % 10) {
                return false;
            }
            original /= 10;
        }

        return true;
    }

    public static void main(String[] args) {
        int num1 = 121;
        int num2 = -121;
        int num3 = 123;

        System.out.println(isPalindrome(num1)); // true
        System.out.println(isPalindrome(num2)); // false
        System.out.println(isPalindrome(num3)); // false
    }
}

Explanation:

We use a stack to store the digits of the number in reverse order.
We compare the popped digits with the original number, digit by digit.

Time Complexity:

The time complexity is O(n) due to iterating through the digits.
The space complexity is O(n) due to the stack storing the digits.

Palindrome Number Java Leetcode Solution Using Queue

A queue can be used to check for palindromes by storing the digits in a first-in-first-out (FIFO) order and comparing the digits from both ends.

import java.util.LinkedList;
import java.util.Queue;

public class PalindromeNumber {

    public static boolean isPalindrome(int num) {
        if (num < 0) return false; // Negative numbers are not palindromes
        
        Queue<Integer> queue = new LinkedList<>();
        int original = num;
        
        // Store digits in the queue
        while (num > 0) {
            queue.offer(num % 10);
            num /= 10;
        }

        // Compare digits from both ends
        while (original > 0) {
            if (queue.poll() != original % 10) {
                return false;
            }
            original /= 10;
        }

        return true;
    }

    public static void main(String[] args) {
        int num1 = 121;
        int num2 = -121;
        int num3 = 123;

        System.out.println(isPalindrome(num1)); // true
        System.out.println(isPalindrome(num2)); // false
        System.out.println(isPalindrome(num3)); // false
    }
}

Explanation:

We store digits of the number in the queue.
We compare the digits from the front and rear of the queue with the original number.

Time Complexity:

The time complexity is O(n) due to iterating through the digits.
The space complexity is O(n) due to the queue storing the digits.

Conclusion

In this article, we have explored multiple solutions to the Palindrome Number Leetcode problem in Java. We began with the naive solution using string manipulation, then discussed an intermediate solution using mathematical operations and an optimal solution that reverses only half the number for better performance. Additionally, we explored solutions involving stacks and queues for a different perspective.

By understanding these various approaches, you can choose the best solution depending on the problem requirements and constraints, such as memory usage, execution time, and code readability. Whether you are a beginner or an advanced developer, tackling the palindrome number problem will enhance your problem-solving skills in Java.

That’s all on the Palindrome Number Java Leetcode solutions.

To keep yourself up to date with our latest content, please subscribe to our newsletter by dropping your email address here: Signup for Our Newsletter.

Please follow us on Medium.