Palindrome Number LeetCode 9 Deep Dive

LeetCode 9 — Palindrome Number — gives you an integer x and asks you to return true if x is a palindrome, and false otherwise. A palindrome reads the same forwards and backwards: 121 is a palindrome, -121 is not (it reads -121 forward but 121- backward), and 10 is not (it reads 01 backward, and integers do not have leading zeros). The problem includes a follow-up: can you solve it without converting the integer to a string?

The examples cover the key cases: 121 returns true, -121 returns false, and 10 returns false. The constraint is that x is a 32-bit signed integer, so -2^31 <= x <= 2^31-1. The string-based approach is trivially correct but the follow-up pushes you toward the mathematically elegant reverse-half solution that demonstrates deep understanding of digit manipulation.

Understanding why certain integers are immediate rejects is the first step. Negative numbers always have a leading minus sign which makes them non-palindromes by definition — the digit sequence of a negative number cannot read the same forwards and backwards because the minus appears only at the front. Numbers ending in zero (except zero itself) cannot be palindromes because no integer starts with a leading zero.

Before doing any digit reversal, two quick checks eliminate a large fraction of inputs in O(1). First: if x is negative, return false immediately. A negative number has a leading minus sign, so it cannot be a palindrome — the digit sequence starting from the left begins with minus, but from the right it ends with a digit, so they can never match.

Second: if x ends in zero and x is not zero itself, return false. If the last digit of x is 0, then for x to be a palindrome its first digit would also have to be 0 — but integers do not have leading zeros. The only exception is x == 0 itself, which is a palindrome. The check is: if x != 0 and x % 10 == 0, return false.

Together these two checks — negative and trailing-zero rejects — eliminate all negative numbers and all positive multiples of 10 (10, 20, 100, 1000, etc.) in constant time before any digit processing begins. This is not just an optimization; it also simplifies the main loop by guaranteeing that x is positive and its last digit is nonzero.

The naive approach — reverse all digits of x and compare to the original — risks 32-bit integer overflow if the reversed number is large. For example, reversing 2147483647 (INT_MAX) gives 7463847412, which overflows a 32-bit signed integer. The reverse-half strategy avoids this entirely by reversing only the second half of the number and comparing it to the first half.

The algorithm pops digits from the right of x one at a time using the same pop-and-push technique from Reverse Integer (LeetCode 7): pop the last digit with x % 10, remove it from x with integer division x = x / 10, push it onto the reversed half with reversedHalf = reversedHalf * 10 + digit. Repeat until the reversed half is greater than or equal to the remaining x.

When reversedHalf >= x, the loop stops because we have processed half the digits (or more in the case of an odd-length number where the middle digit ends up in reversedHalf). The comparison then determines if x is a palindrome.

The loop condition x > reversedHalf elegantly signals when half the digits have been processed. At the start, x holds all digits and reversedHalf is 0. Each iteration moves one digit from x to reversedHalf. When reversedHalf catches up to x — i.e., reversedHalf >= x — exactly half the digits (rounded up for odd-length) have been moved.

For even-digit palindromes like 1221: after two iterations x = 12 and reversedHalf = 12. The condition x > reversedHalf is false (12 > 12 is false), so the loop exits. The palindrome check is x == reversedHalf, i.e., 12 == 12 → true. For odd-digit palindromes like 12321: after two iterations x = 12 and reversedHalf = 123. The loop exits because 12 > 123 is false. The middle digit (3, the ones digit of 123) is irrelevant, so we check x == reversedHalf / 10, i.e., 12 == 12 → true.

This works because a palindrome by definition has a symmetric first and second half. By reversing the second half and comparing to the first half, we verify symmetry at the digit level without ever computing the full reversal. The middle digit of an odd-length palindrome can be anything — it pairs with itself — so dividing reversedHalf by 10 strips it cleanly.

Start: x = 12321, reversedHalf = 0. Is x > reversedHalf? 12321 > 0 → yes. Pop last digit: digit = 12321 % 10 = 1. Remove from x: x = 12321 / 10 = 1232. Push to reversed: reversedHalf = 0 * 10 + 1 = 1. State: x = 1232, reversedHalf = 1.

Is x > reversedHalf? 1232 > 1 → yes. Pop: digit = 1232 % 10 = 2. Remove: x = 1232 / 10 = 123. Push: reversedHalf = 1 * 10 + 2 = 12. State: x = 123, reversedHalf = 12.

Is x > reversedHalf? 123 > 12 → yes. Pop: digit = 123 % 10 = 3. Remove: x = 123 / 10 = 12. Push: reversedHalf = 12 * 10 + 3 = 123. State: x = 12, reversedHalf = 123. Is x > reversedHalf? 12 > 123 → no. Loop exits. Odd-length check: x == reversedHalf / 10 → 12 == 123 / 10 → 12 == 12 → true. Answer: true.

Python implementation: def isPalindrome(self, x: int) -> bool: if x < 0 or (x % 10 == 0 and x != 0): return False; reversed_half = 0; while x > reversed_half: reversed_half = reversed_half * 10 + x % 10; x //= 10; return x == reversed_half or x == reversed_half // 10. The floor division //= ensures x stays an integer as digits are removed. The final return handles both even (x == reversed_half) and odd (x == reversed_half // 10) length numbers in a single expression.

Java implementation: public boolean isPalindrome(int x) { if (x < 0 || (x % 10 == 0 && x != 0)) return false; int reversedHalf = 0; while (x > reversedHalf) { reversedHalf = reversedHalf * 10 + x % 10; x /= 10; } return x == reversedHalf || x == reversedHalf / 10; } Java integer division truncates toward zero, so x /= 10 and reversedHalf / 10 both behave correctly for positive integers. No overflow risk because reversedHalf is always at most half the original magnitude.

Both implementations run in O(log10(n)) time — there are exactly as many loop iterations as half the digit count of x — and use O(1) extra space. No strings, arrays, or auxiliary data structures. The time complexity is technically O(log10(n) / 2) but simplifies to O(log n). The space complexity is O(1) regardless of input magnitude.

Reverse Integer — LeetCode 7 — is the direct predecessor and teaches the pop-and-push digit technique used in Palindrome Number. The key difference is that Reverse Integer reverses all digits and must handle 32-bit overflow via a pre-push check, while Palindrome Number reverses only half the digits which sidesteps overflow entirely. Mastering LeetCode 7 first makes LeetCode 9 significantly easier to understand.

Happy Number — LeetCode 202 — uses the same digit-extraction loop (digit = n % 10, n = n / 10) to compute the sum of squares of digits, detecting a cycle with Floyd's slow-and-fast pointer technique. The digit manipulation pattern is identical; only the aggregation operation changes from reversed-number construction to sum-of-squares. Palindrome Linked List — LeetCode 234 — is the analogous palindrome check for linked lists, using the reverse-second-half technique applied to nodes rather than digits.

Together the number math family — LeetCode 7, 9, 202, and 234 — covers the complete toolkit: digit extraction with modulo and integer division, reversal with pop-and-push, overflow prevention by reversing only part of the input, cycle detection, and the palindrome check pattern. These problems appear frequently in coding interviews and their techniques recur as subroutines in harder problems involving number theory and math reasoning.