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

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:
Handle Negative Numbers: Any negative number cannot be a palindrome. Why? Because the negative sign breaks the symmetry.
-121
becomes121-
when reversed. So, ifx
is less than 0, we immediately returnfalse
.Convert to String: Transform the integer into its string representation. This makes it easy to reverse.
Reverse the String: Reverse the newly created string.
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:
Initial Checks:
Just like before, negative numbers are out.
A new crucial check: if a number ends in
0
(like120
), and it's not0
itself, it cannot be a palindrome. Why? Because its reverse would start with0
(e.g.,021
), which is not how numbers are typically represented.0
itself is a palindrome.
Reversing Half the Number:
We use a
while
loop that continues as long asx
(our original number) is greater thanrevertedNumber
.Inside the loop:
revertedNumber = revertedNumber * 10 + x % 10;
: This line does two things:x % 10
extracts the last digit ofx
.revertedNumber * 10
shifts the existingrevertedNumber
one place to the left, making space for the new digit.We then add the extracted last digit to
revertedNumber
.
x = (int)(x / 10);
(orx //= 10
in Python,x /= 10
in Java/JS): This line removes the last digit fromx
, effectively "shortening" the original number.
The Comparison:
The loop stops when
x
becomes less than or equal torevertedNumber
. 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 whenx
becomes equal torevertedNumber
(e.g.,x
becomes12
,revertedNumber
becomes12
). In this case,x == revertedNumber
will betrue
.Case 2: Odd Number of Digits: If the original number had an odd number of digits (e.g.,
12321
), the loop will stop whenx
has one more digit thanrevertedNumber
(e.g.,x
becomes12
,revertedNumber
becomes123
). The middle digit is now inrevertedNumber
. To account for this, we checkx == (int)(revertedNumber / 10)
. DividingrevertedNumber
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.
Subscribe to my newsletter
Read articles from Nature directly inside your inbox. Subscribe to the newsletter, and don't miss out.
Written by
