LeetCode 9 – Palindrome Number

Palindrome Number is trivial if you are allowed to call toString, which is why the follow-up — "could you solve it without converting the integer to a string?" — is the actual question. The neat answer reverses only half the number, which sidesteps the overflow problem that reversing the whole thing would create.

The problem

Return true if an integer reads the same backwards as forwards.

121   -> true
-121  -> false     reads "121-" backwards
10    -> false     reads "01" backwards
0     -> true

Two answers you can rule out immediately

Convert to a string and compare with its reverse. Correct, two lines, and it uses O(log n) space. Say it, then say the follow-up forbids it.

Reverse the whole integer and compare. The natural next thought, and it has a real flaw: the reversal of a valid int can overflow, so you would need the same overflow dance as Reverse Integer just to answer a yes/no question. Reversing half the number cannot overflow at all, because half a number's digits always fit.

The idea: reverse half, then meet in the middle

Peel digits off the right-hand end into a growing reversed, while the original x shrinks from the right. Once reversed has caught up with — become at least as large as — the remaining x, you are at the midpoint, and the two halves are sitting in the two variables ready to compare.

x = 1221                    x = 12321
  x=122   reversed=1          x=1232  reversed=1
  x=12    reversed=12         x=123   reversed=12
  stop: 12 == 12  -> true     x=12    reversed=123
                              stop: 12 == 123 / 10  -> true

The odd-length case is why the return has two halves. With an odd digit count, the middle digit gets swept into reversed and belongs to neither side — so reversed / 10 drops it, and the comparison works again.

The two guards up front

The loop needs both of these before it can run, and the second one is easy to miss:

• x < 0 — a negative number is never a palindrome, because the minus sign is only on one end. This also protects the loop, which would never terminate on a negative input.
• x % 10 == 0 && x != 0 — a number ending in zero could only be a palindrome if it started with zero, and integers do not. Without this, 10 reverses to 01 == 1, the loop stops with x = 1 and reversed = 1, and it wrongly reports true. The x != 0 half of the guard is there because 0 itself is a palindrome.

Java

class Solution {
    public boolean isPalindrome(int x) {
        // Negative: the sign is only on one end. Trailing zero: would need a leading
        // zero to match, which integers do not have. Zero itself is a palindrome.
        if (x < 0 || (x % 10 == 0 && x != 0)) {
            return false;
        }

        int reversed = 0;
        while (x > reversed) {          // stop at the midpoint
            reversed = reversed * 10 + x % 10;
            x /= 10;
        }

        // Even digit count: the halves are equal.
        // Odd digit count: reversed holds the extra middle digit, so drop it.
        return x == reversed || x == reversed / 10;
    }
}

Python

class Solution:
    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:
            x, digit = divmod(x, 10)
            reversed_half = reversed_half * 10 + digit

        return x == reversed_half or x == reversed_half // 10

Complexity

O(log₁₀ x) time — and only half as many iterations as reversing the whole number — with O(1) space. That constant space is the entire point of the follow-up; the string solution is the same asymptotic time but allocates.

What the interviewer is checking

• That you reach for the half-reversal rather than reversing everything, and can explain that it is the version that cannot overflow.
• That you produce the trailing-zero guard without being shown a failing test.
• That you handle the odd digit count — 12321 is the test case.
• That 0 returns true and does not fall foul of your own guard.