Leet Code Palindrome problem in Javascript

General Idea

Given an integer, return whether true or false if it is a palindrome.

** Approach 1
So the easiest way to approach this is to convert the number into a string, break into an array, reverse the array, then join back the string and compare the original string and reversed string. Lets try this first and look at the Time and Space Complexity.

export function isPalindrome(x: number): boolean {
  // Convert number to string
  const numStr = x.toString(); // O(1)

  // Get reversed string
  const reversedString = numStr.split("").reverse().join("");

  // Compare original and reversed strings
  return numStr === reversedString;
}

Approach 1 Complexity

Time Complexity is O(n)

1. So when we convert the input integer to a string, it depends on the size of integer so O(n)

2. Then we break the string into an array, so again O(n)

3. Then we reverse array O(n)

4. Join the reversed array above into a string O(n)

5. Compare the 2 strings O(n)

So O(n) + O(n) + O(n) + O(n) + O(n) = O(n).

Even though there are 5 different O(n) operations, we simplify it to just O(n) because:

Constants don't matter in Big O notation - whether an algorithm takes n steps or 5n steps, the growth rate is still linear with respect to the input size.

We care about the algorithmic scaling behavior as n gets very large, and at that point, the difference between n and 5n becomes negligible

Space Complexity is O(n)
We create additional strings and arrays:

1. We create a new string numStr from the original integer O(n)

2. we create a new array from split O(n)

3. We have a reversed str O(n)

The solution is simple but not the most efficient for space complexity.

** Approach 2 More Efficient and what we want.

Let's look at a more optimized solution that avoids string conversion and uses a mathematical approach.

Approach 2 Complexity

Time Complexity: O(log n)

We only process half the digits
For a number n, the number of digits is log₁₀(n)
Each iteration processes one digit

Space Complexity: O(1)

We only use two variables regardless of input size:

x (which we modify)
reversedHalf

Key optimizations:

Early returns for negative numbers and single digits
Only reverses half the number instead of the entire number
No string conversion needed
Handles both even and odd length numbers
Uses constant extra space

Example of how it works for number 1221:

Initially: x = 1221, reversedHalf = 0
First iteration: x = 122, reversedHalf = 1
Second iteration: x = 12, reversedHalf = 12
Loop ends as x ≤ reversedHalf
Check if x === reversedHalf (12 === 12) → true