LeetCode #9 Solved: Palindrome Number

The Palindrome Number problem on LeetCode seems pretty easy to solve. You just need to check if the number reads the same from both ends (which is what a palindrome is). It's easy to come up with a solution that takes O(n) time, but you can actually reduce the runtime to O(logn) easily. Like I did in my last post, this time, too, I'll walk you through both the approaches, so let's start!

Naive Approach

In this problem, we're given an integer, and we need to find if it's a palindrome. The easiest way to do so is to simply convert the integer into a string (variable s in the example below), and then initialize another variable with the reversed string (variable t in the example below). You can simply use built-in JS functions to make things easier for yourself. Then, we just need to check if the two strings are equal.

var isPalindrome = function(x) {
    let s = x.toString();
    let t = s.split("").reverse().join("");
    return s === t;
};

However, the runtime complexity of this code is O(n) where n is the number of digits in the integer. This is because all the string methods in this code (split(), reverse(), and join()) take O(n) time. Here's why:

• .split("") iterates through every character in the string and creates a new array with each character. Since it's going to iterate over all the characters once, the time complexity is directly proportional to the string's length (n), resulting in a time complexity of O(n).

• .reverse() involves swapping the positions of elements. The number of swaps is proportional to half the elements in the array (usually there are two pointers at the two ends of the array and both move towards the center, swapping the elements until they meet in the middle, but the implementation can vary) which means the time complexity is O(n/2) but since we drop the constants, the runtime comes out to be O(n).

• .join("") concatenates each element of an array into a single string. Since it iterates over all the elements and performs the concatenation, the time complexity depends on the number of elements in the array (n) that must be joined. So, for this operation, the time complexity is O(n).

However, a more optimized approach is to solve the problem without converting the integer into a string. And that's something that LeetCode hints at too:

Optimized Approach

The optimized approach involves using the integer directly without converting it into a string. To get started, we already know that if the number is negative or if it ends with a zero (but is not zero), then it won't be a palindrome. So we can take care of these cases first:

  if (x < 0 || (x % 10 === 0 && x !== 0)) {
        return false;

With these out of the way, we can now focus on positive integers that don't end with 0. This involves a little bit of math - the key to reversing a number is to use two operations: % and /, and we can understand this reversal better with an example.

Let's assume we have the number 1221, and to check if this is a palindrome, we just need to reverse the first half, and see if it's equal to the second half.

To do so, we first need the right-most digit, and we can do that by finding the remainder using %: 1221%10 = 1. Now that we have 1, we need 2 next, and to do that, we can perform the same remainder operation on 122. This means we need to get 122 from 1221 somehow, and that's easy - just do Math.floor(1221/10), and we get 122, and by doing 122%10, we get 2. Now, we just need to combine the 1 and 2.

We know that reversing 21 (the second half of the number) will give us 12 (the first half of the number) and if we need to put together the 1 and 2 we've separated, we just need to do 1*10 + 2 (122%10) to get 10+2=12. All that's left to do is check if x === reversed.

Converting this into code, we get:

  let reversed = 0;
    while (x > reversed) {
        reversed = (reversed * 10) + (x % 10);
        x = Math.floor(x / 10);
    } 
return x === reversed

Keeping the example in mind, here's a visualization to make the code clearer:

After the second iteration, the program will quit the loop, and we'll be left with two variables: reversed (the second half of the original number) and x (the first half of the original number). All that's left to do is return x === reversed and it'll return true if both are equal.

But what about odd number of digits?

The code above won't give you the right answer if you use it for an odd number of digits. And we can try to work that out with another example. Let's take 121 as our example.

After the second iteration, the program will quit the loop, and in the end you'll be left with x = 1 and reversed = 12, and when you do return x === reversed, you'll get false, even though you know that 121 is a palindrome, and should return true.

To take care of cases where the input has an odd number of digits, we can compare x and Math.floor(reversed/10) to see if they're equal. What we're basically doing is removing the middle digit of the original number (the last digit of our reversed number, which is 2 in this case) by dividing reversed by 10 and taking the floor of the result. So, Math.floor(12/10) gives us 1, and we can compare that with x to check if the numbers before and after the middle digit are equal. In code, this means:

return x === Math.floor(reversed/10);

If you're having difficulty understanding this, try to dry-run the code with a five-digit palindrome, like 12321, and you'll understand the concept better. Now all that's left to do is put the whole code together and you'll get:

var isPalindrome = function(x){
      if (x < 0 || (x % 10 === 0 && x !== 0)) {
        return false;
    }

    let reversed = 0;
    while (x > reversed) {
        reversed = (reversed * 10) + (x % 10);
        x = Math.floor(x / 10);
    }

    return x === reversed || x === Math.floor(reversed / 10);
}

And that's it - you've optimized the solution! The runtime for this solution is O(logx) because at each iteration of the while loop, we reduce the number of digits by 1 (by dividing by 10) which means the maximum number of iterations is equal to the log (to the base 10) of the number of digits in x. In other words, the runtime is O(log10(x)) and since we drop all the constant factors, the final runtime comes out to be O(log(x)). Hope that makes sense!

As always, you can run this code directly on OneCompiler or find it on my GitHub. The next problem I'm going to solve is LeetCode #13: Roman to Integer, so stay tuned!

Solving Leetcode problems is hard enough as it is, and add to that the difficulty of finding an in-depth solution that explains everything, and you find yourself stuck. Some videos are hard to follow, some don't explain the basics, while others leave you with more questions than answers. In this series, I break down Leetcode problems one at a time and walk you through a step-by-step solution. Have a question you can't understand? Send it to me, and I'll explain it in detail. And don't forget to subscribe to my newsletter to get my articles directly into your inbox!