This content originally appeared on DEV Community and was authored by sushmeet sunger
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)
So when we convert the input integer to a string, it depends on the size of integer so O(n)
Then we break the string into an array, so again O(n)
Then we reverse array O(n)
Join the reversed array above into a string O(n)
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:
We create a new string
numStrfrom the original integer O(n)we create a new array from split O(n)
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
This content originally appeared on DEV Community and was authored by sushmeet sunger
sushmeet sunger | Sciencx (2025-02-12T19:50:17+00:00) Leet Code Palindrome problem in Javascript. Retrieved from https://www.scien.cx/2025/02/12/leet-code-palindrome-problem-in-javascript/
Please log in to upload a file.
There are no updates yet.
Click the Upload button above to add an update.