Step-by-Step Guide to LeetCode's Palindrome Problem

NatureNature
9 min read

LeetCode's Palindrome Number Problem

Ever wondered if a number reads the same forwards and backward? That's the essence of a palindrome! Today, we're going to tackle a classic coding challenge that popped up on our screen: LeetCode's "9. Palindrome Number."

What's the Problem All About?

The challenge is straightforward: given an integer x, determine if it's a palindrome.

  • Example 1: x = 121

    • Reads 121 from left to right.

    • Reads 121 from right to left.

    • Output: true (It's a palindrome!)

  • Example 2: x = -121

    • Reads -121 from left to right.

    • Reads 121- from right to left.

    • Output: false (Not a palindrome, because of the negative sign!)

  • Example 3: x = 10

    • Reads 10 from left to right.

    • Reads 01 from right to left.

    • Output: false (Not a palindrome!)

The Simple Approach (and Why It's Often a Good Start!)

The most intuitive way to solve this problem is to convert the number into a string and then check if the string is the same when reversed.

Let's break down the logic:

  1. Handle Negative Numbers: Any negative number cannot be a palindrome. Why? Because the negative sign breaks the symmetry. -121 becomes 121- when reversed. So, if x is less than 0, we immediately return false.

  2. Convert to String: Transform the integer into its string representation. This makes it easy to reverse.

  3. Reverse the String: Reverse the newly created string.

  4. Compare: Compare the original string with the reversed string. If they are identical, then the number is a palindrome!

Optimized Code (with Comments!)

While the string conversion method is easy to understand, we can often do better, especially in interviews. A more optimized approach involves reversing half of the number without converting it to a string, avoiding extra memory allocation.

PHP

<?php

class Solution {

    /**
     * @param Integer $x
     * @return Boolean
     */
    function isPalindrome($x) {
        // Step 1: Handle negative numbers. Negative numbers cannot be palindromes.
        if ($x < 0) {
            return false;
        }

        // Step 2: Convert the integer to a string.
        $original = strval($x);

        // Step 3: Reverse the string.
        $reversed = strrev($original);

        // Step 4: Compare the original and reversed strings.
        return $original === $reversed;
    }
}

// --- Optimized PHP Solution (without string conversion for numbers) ---
class OptimizedSolution {
    /**
     * @param Integer $x
     * @return Boolean
     */
    function isPalindrome($x) {
        // Edge cases:
        // 1. Negative numbers are not palindromes.
        // 2. Numbers ending in 0 (except 0 itself) cannot be palindromes
        //    because the reversed number would start with 0.
        if ($x < 0 || ($x % 10 == 0 && $x != 0)) {
            return false;
        }

        $revertedNumber = 0;
        // Keep looping as long as the original number is greater than the reverted number.
        // This effectively reverses only half of the number.
        while ($x > $revertedNumber) {
            // Get the last digit of x and append it to revertedNumber.
            $revertedNumber = $revertedNumber * 10 + ($x % 10);
            // Remove the last digit from x.
            $x = (int)($x / 10); // Use (int) for integer division
        }

        // When the length of the number is odd, the middle digit will be in the original x,
        // so we divide revertedNumber by 10 to remove the last digit (which is the middle digit).
        // If the length is even, x and revertedNumber will be equal.
        return $x == $revertedNumber || $x == (int)($revertedNumber / 10);
    }
}
?>

Java

class Solution {
    public boolean isPalindrome(int x) {
        // Step 1: Handle negative numbers. Negative numbers cannot be palindromes.
        if (x < 0) {
            return false;
        }

        // Step 2: Convert the integer to a string.
        String original = String.valueOf(x);

        // Step 3: Reverse the string.
        StringBuilder reversed = new StringBuilder(original).reverse();

        // Step 4: Compare the original and reversed strings.
        return original.equals(reversed.toString());
    }
}

// --- Optimized Java Solution (without string conversion) ---
class OptimizedSolutionJava {
    public boolean isPalindrome(int x) {
        // Edge cases:
        // 1. Negative numbers are not palindromes.
        // 2. Numbers ending in 0 (except 0 itself) cannot be palindromes
        //    because the reversed number would start with 0.
        if (x < 0 || (x % 10 == 0 && x != 0)) {
            return false;
        }

        int revertedNumber = 0;
        // Keep looping as long as the original number is greater than the reverted number.
        // This effectively reverses only half of the number.
        while (x > revertedNumber) {
            // Get the last digit of x and append it to revertedNumber.
            revertedNumber = revertedNumber * 10 + x % 10;
            // Remove the last digit from x.
            x /= 10;
        }

        // When the length of the number is odd, the middle digit will be in the original x,
        // so we divide revertedNumber by 10 to remove the last digit (which is the middle digit).
        // If the length is even, x and revertedNumber will be equal.
        return x == revertedNumber || x == revertedNumber / 10;
    }
}

Python

class Solution:
    def isPalindrome(self, x: int) -> bool:
        # Step 1: Handle negative numbers. Negative numbers cannot be palindromes.
        if x < 0:
            return False

        # Step 2: Convert the integer to a string.
        original = str(x)

        # Step 3: Reverse the string. Python's slicing is very concise for this.
        reversed_str = original[::-1]

        # Step 4: Compare the original and reversed strings.
        return original == reversed_str

# --- Optimized Python Solution (without string conversion) ---
class OptimizedSolutionPython:
    def isPalindrome(self, x: int) -> bool:
        # Edge cases:
        # 1. Negative numbers are not palindromes.
        # 2. Numbers ending in 0 (except 0 itself) cannot be palindromes
        #    because the reversed number would start with 0.
        if x < 0 or (x % 10 == 0 and x != 0):
            return False

        reverted_number = 0
        # Keep looping as long as the original number is greater than the reverted number.
        # This effectively reverses only half of the number.
        while x > reverted_number:
            # Get the last digit of x and append it to reverted_number.
            reverted_number = reverted_number * 10 + x % 10
            # Remove the last digit from x (integer division).
            x //= 10

        # When the length of the number is odd, the middle digit will be in the original x,
        # so we divide reverted_number by 10 to remove the last digit (which is the middle digit).
        # If the length is even, x and reverted_number will be equal.
        return x == reverted_number or x == reverted_number // 10

JavaScript

/**
 * @param {number} x
 * @return {boolean}
 */
var isPalindrome = function(x) {
    // Step 1: Handle negative numbers. Negative numbers cannot be palindromes.
    if (x < 0) {
        return false;
    }

    // Step 2: Convert the integer to a string.
    let original = String(x);

    // Step 3: Reverse the string.
    let reversed = original.split('').reverse().join('');

    // Step 4: Compare the original and reversed strings.
    return original === reversed;
};

// --- Optimized JavaScript Solution (without string conversion) ---
/**
 * @param {number} x
 * @return {boolean}
 */
var isPalindromeOptimized = function(x) {
    // Edge cases:
    // 1. Negative numbers are not palindromes.
    // 2. Numbers ending in 0 (except 0 itself) cannot be palindromes
    //    because the reversed number would start with 0.
    if (x < 0 || (x % 10 === 0 && x !== 0)) {
        return false;
    }

    let revertedNumber = 0;
    // Keep looping as long as the original number is greater than the reverted number.
    // This effectively reverses only half of the number.
    while (x > revertedNumber) {
        // Get the last digit of x and append it to revertedNumber.
        revertedNumber = revertedNumber * 10 + (x % 10);
        // Remove the last digit from x (integer division).
        x = Math.floor(x / 10);
    }

    // When the length of the number is odd, the middle digit will be in the original x,
    // so we divide revertedNumber by 10 to remove the last digit (which is the middle digit).
    // If the length is even, x and revertedNumber will be equal.
    return x === revertedNumber || x === Math.floor(revertedNumber / 10);
};

Explaining the Optimized Approach (The "Reverse Half" Method)

The optimized solutions above avoid string conversions by playing with numbers directly. Here's a breakdown:

  1. Initial Checks:

    • Just like before, negative numbers are out.

    • A new crucial check: if a number ends in 0 (like 120), and it's not 0 itself, it cannot be a palindrome. Why? Because its reverse would start with 0 (e.g., 021), which is not how numbers are typically represented. 0 itself is a palindrome.

  2. Reversing Half the Number:

    • We use a while loop that continues as long as x (our original number) is greater than revertedNumber.

    • Inside the loop:

      • revertedNumber = revertedNumber * 10 + x % 10;: This line does two things:

        • x % 10 extracts the last digit of x.

        • revertedNumber * 10 shifts the existing revertedNumber one place to the left, making space for the new digit.

        • We then add the extracted last digit to revertedNumber.

      • x = (int)(x / 10); (or x //= 10 in Python, x /= 10 in Java/JS): This line removes the last digit from x, effectively "shortening" the original number.

  3. The Comparison:

    • The loop stops when x becomes less than or equal to revertedNumber. At this point, we've effectively reversed half of the original number.

    • Case 1: Even Number of Digits: If the original number had an even number of digits (e.g., 1221), the loop will stop when x becomes equal to revertedNumber (e.g., x becomes 12, revertedNumber becomes 12). In this case, x == revertedNumber will be true.

    • Case 2: Odd Number of Digits: If the original number had an odd number of digits (e.g., 12321), the loop will stop when x has one more digit than revertedNumber (e.g., x becomes 12, revertedNumber becomes 123). The middle digit is now in revertedNumber. To account for this, we check x == (int)(revertedNumber / 10). Dividing revertedNumber by 10 removes its last digit (the middle digit), allowing us to compare the remaining halves.

This optimized approach is generally preferred as it avoids the overhead of string conversions and can be more efficient for very large numbers.

Why Does This Matter?

Understanding problems like "Palindrome Number" is crucial for several reasons:

  • Foundation of Algorithms: It teaches fundamental concepts like number manipulation, string operations, and conditional logic.

  • Problem-Solving Skills: Breaking down a problem into smaller, manageable steps is a core skill for any programmer.

  • Interview Preparation: These types of questions are common in technical interviews, assessing your analytical thinking and coding proficiency.

  • Optimization: Learning to go beyond the most straightforward solution and think about efficiency is a valuable habit.

So, the next time you encounter a number, take a moment to ponder: is it a palindrome? With these techniques, you're well-equipped to find out! Happy.

0
Subscribe to my newsletter

Read articles from Nature directly inside your inbox. Subscribe to the newsletter, and don't miss out.

pallindrome2Articles1Weekleetcodeleetcode-solutionProblem Solving

Written by

Nature
Nature