LeetCode 564 - Find the Closest Palindrome
The problem gives us a string n representing a positive integer, and asks us to find the numerically closest palindrome that is not equal to the original number itself. A palindrome is a number that reads the same forward and backward. Examples include 121, 999, and 1331.
Difficulty: 🔴 Hard
Topics: Math, String
Solution
Problem Understanding
The problem gives us a string n representing a positive integer, and asks us to find the numerically closest palindrome that is not equal to the original number itself.
A palindrome is a number that reads the same forward and backward. Examples include 121, 999, and 1331.
The key requirement is that we minimize the absolute difference:
$$|candidate - original|$$
If two palindromes are equally close, we must return the smaller one.
The input is provided as a string instead of an integer because the value can be extremely large, up to $10^{18} - 1$. This exceeds the safe integer range in some languages and also hints that the solution should focus on digit manipulation rather than brute force numeric iteration.
The constraints tell us several important things:
- The length of
ncan be up to 18 digits. - The number always has no leading zeros.
- The number is always valid and positive.
These constraints immediately eliminate any approach that searches outward one number at a time. In the worst case, the gap between palindromes could be extremely large.
Several edge cases are especially important:
- Single digit numbers such as
"1"or"9" - Numbers like
"10"or"1000"where the closest palindrome has fewer digits - Numbers like
"99"or"999"where the closest palindrome has more digits - Numbers that are already palindromes, because we cannot return the number itself
- Tie situations where two palindromes are equally distant
For example:
"1000"has nearby palindromes999and1001, both distance 1, so we return999"1"has nearby palindromes0and2, both distance 1, so we return0
Understanding how palindromes are formed is the key to solving this efficiently.
Approaches
Brute Force Approach
The most direct solution is to repeatedly search outward from the given number.
We could:
- Convert the input string into an integer.
- Check
num - 1,num + 1,num - 2,num + 2, and so on. - For each value, test whether it is a palindrome.
- Return the first palindrome found with minimum distance.
A palindrome check is straightforward by converting the number to a string and comparing it with its reverse.
This approach is correct because eventually we will encounter the nearest palindrome. However, it is far too slow for the given constraints.
Consider a large 18 digit number. The gap between palindromes can be substantial, and repeatedly checking numbers one by one becomes infeasible.
Key Insight for the Optimal Approach
A palindrome is completely determined by its first half.
For example:
12321is determined by1234554is determined by45
Instead of searching all nearby integers, we only need to generate a small set of plausible palindrome candidates.
The nearest palindrome must come from one of these categories:
- Mirroring the current first half directly
- Mirroring the first half after incrementing it by 1
- Mirroring the first half after decrementing it by 1
- Special boundary palindromes:
999...9991000...0001
Why do these work?
Because changing digits far away from the center causes much larger numeric differences. The nearest palindrome almost always differs only near the middle digits.
This reduces the problem from searching potentially billions of numbers to checking only a handful of candidates.
Approach Comparison
| Approach | Time Complexity | Space Complexity | Notes |
|---|---|---|---|
| Brute Force | O(k × d) | O(d) | Searches outward checking every nearby number |
| Optimal | O(d) | O(d) | Generates only a few valid palindrome candidates |
Here:
dis the number of digitskis the distance to the nearest palindrome
Algorithm Walkthrough
Step 1: Convert the Input Number
Convert the input string into an integer so we can compute numeric differences between candidates and the original value.
We still keep the original string because digit manipulation is easier with strings.
Step 2: Generate Boundary Candidates
There are two extremely important edge palindromes:
- The largest palindrome with one fewer digit:
$$10^{len(n)-1} - 1$$
Examples:
999999
- The smallest palindrome with one more digit:
$$10^{len(n)} + 1$$
Examples:
100110001
These handle cases like:
"1000"→ nearest could be999"999"→ nearest could be1001
Without these special candidates, many edge cases fail.
Step 3: Extract the Prefix
Take the first half of the number.
For a number of length L, the prefix length is:
$$(L + 1) // 2$$
Examples:
| Number | Prefix |
|---|---|
| 12345 | 123 |
| 4567 | 45 |
The prefix contains enough information to reconstruct the palindrome.
Step 4: Create Nearby Prefix Variants
Generate three prefixes:
prefix - 1prefixprefix + 1
These represent the only realistic nearby palindrome structures.
For example:
-
Original:
12345 -
Prefix:
123 -
Candidates built from:
-
122 -
123 -
124
Step 5: Mirror Each Prefix
Construct palindromes by mirroring the prefix.
For odd length numbers:
- Mirror everything except the last digit
Example:
- Prefix
123 - Result
12321
For even length numbers:
- Mirror the entire prefix
Example:
- Prefix
45 - Result
4554
Step 6: Remove the Original Number
If the input itself is a palindrome, it may appear in the candidate set. We must exclude it because the problem explicitly forbids returning the original number.
Step 7: Select the Best Candidate
Among all candidates:
- Choose the one with minimum absolute difference
- If there is a tie, choose the smaller value
This exactly matches the problem definition.
Why it works
The nearest palindrome must preserve most leading digits of the original number. Large changes in the left side create much larger numeric differences than small changes near the center.
By mirroring the current prefix and its immediate neighbors, we cover all possible closest palindrome structures. The two additional boundary candidates handle digit-length transitions such as 999 and 1000.
Because every possible closest palindrome is included in this small candidate set, selecting the minimum difference guarantees correctness.
Python Solution
class Solution:
def nearestPalindromic(self, n: str) -> str:
length = len(n)
original = int(n)
candidates = set()
# Edge case candidates
candidates.add(10 ** (length - 1) - 1)
candidates.add(10 ** length + 1)
# First half of the number
prefix_length = (length + 1) // 2
prefix = int(n[:prefix_length])
# Generate palindromes from prefix - 1, prefix, prefix + 1
for delta in (-1, 0, 1):
new_prefix = str(prefix + delta)
if length % 2 == 0:
palindrome = new_prefix + new_prefix[::-1]
else:
palindrome = new_prefix + new_prefix[:-1][::-1]
candidates.add(int(palindrome))
# Remove the original number itself
candidates.discard(original)
best = None
for candidate in candidates:
difference = abs(candidate - original)
if best is None:
best = candidate
else:
best_difference = abs(best - original)
if difference < best_difference:
best = candidate
elif difference == best_difference and candidate < best:
best = candidate
return str(best)
The implementation begins by determining the length of the input and converting the original number into an integer for arithmetic comparisons.
A set is used for candidate storage because multiple construction paths can generate the same palindrome. Using a set automatically removes duplicates.
The two boundary candidates are inserted first. These are critical for handling digit count transitions.
Next, the code extracts the prefix that determines the palindrome structure. The expression (length + 1) // 2 ensures that odd length numbers include the middle digit in the prefix.
The loop over (-1, 0, 1) creates nearby prefixes. Each prefix is mirrored differently depending on whether the number length is even or odd.
For even lengths, the entire prefix is mirrored.
For odd lengths, the last digit is skipped during mirroring to avoid duplicating the center digit.
After generating all candidates, the original number is removed because it cannot be returned.
Finally, the algorithm scans all candidates and selects the best one using the problem's comparison rules:
- Smaller absolute difference wins
- If tied, smaller numeric value wins
Go Solution
package main
import (
"math"
"strconv"
)
func nearestPalindromic(n string) string {
length := len(n)
original, _ := strconv.ParseInt(n, 10, 64)
candidates := make(map[int64]bool)
// Edge candidates
candidates[int64(math.Pow10(length-1))-1] = true
candidates[int64(math.Pow10(length))+1] = true
prefixLength := (length + 1) / 2
prefix, _ := strconv.ParseInt(n[:prefixLength], 10, 64)
for _, delta := range []int64{-1, 0, 1} {
newPrefix := strconv.FormatInt(prefix+delta, 10)
var palindrome string
if length%2 == 0 {
palindrome = newPrefix + reverse(newPrefix)
} else {
palindrome = newPrefix + reverse(newPrefix[:len(newPrefix)-1])
}
value, _ := strconv.ParseInt(palindrome, 10, 64)
candidates[value] = true
}
delete(candidates, original)
var best int64 = -1
for candidate := range candidates {
diff := abs(candidate - original)
if best == -1 {
best = candidate
continue
}
bestDiff := abs(best - original)
if diff < bestDiff ||
(diff == bestDiff && candidate < best) {
best = candidate
}
}
return strconv.FormatInt(best, 10)
}
func reverse(s string) string {
runes := []rune(s)
left := 0
right := len(runes) - 1
for left < right {
runes[left], runes[right] = runes[right], runes[left]
left++
right--
}
return string(runes)
}
func abs(x int64) int64 {
if x < 0 {
return -x
}
return x
}
The Go implementation follows the same logic as the Python version, but there are a few language-specific details worth noting.
Go does not have a built-in string reverse operation, so a helper function is implemented manually.
The solution uses int64 because the input range fits safely within signed 64 bit integers.
A map[int64]bool is used instead of a set, since Go does not provide a native set type.
The palindrome construction logic is identical to the Python version, including separate handling for even and odd lengths.
Worked Examples
Example 1
Input:
n = "123"
Step 1: Initial Values
| Variable | Value |
|---|---|
| length | 3 |
| original | 123 |
| prefixLength | 2 |
| prefix | 12 |
Step 2: Boundary Candidates
| Candidate |
|---|
| 99 |
| 1001 |
Step 3: Generate Prefix Variants
| Delta | New Prefix | Palindrome |
|---|---|---|
| -1 | 11 | 111 |
| 0 | 12 | 121 |
| 1 | 13 | 131 |
Candidate set:
| Candidates |
|---|
| 99 |
| 111 |
| 121 |
| 131 |
| 1001 |
Step 4: Compute Differences
| Candidate | Difference |
|---|---|
| 99 | 24 |
| 111 | 12 |
| 121 | 2 |
| 131 | 8 |
| 1001 | 878 |
The minimum difference is 2.
Final answer:
121
Example 2
Input:
n = "1"
Step 1: Initial Values
| Variable | Value |
|---|---|
| length | 1 |
| original | 1 |
| prefixLength | 1 |
| prefix | 1 |
Step 2: Boundary Candidates
| Candidate |
|---|
| 0 |
| 11 |
Step 3: Generate Prefix Variants
| Delta | New Prefix | Palindrome |
|---|---|---|
| -1 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 2 | 2 |
After removing original number 1:
| Candidates |
|---|
| 0 |
| 2 |
| 11 |
Step 4: Compute Differences
| Candidate | Difference |
|---|---|
| 0 | 1 |
| 2 | 1 |
| 11 | 10 |
There is a tie between 0 and 2.
The smaller value is chosen.
Final answer:
0
Complexity Analysis
| Measure | Complexity | Explanation |
|---|---|---|
| Time | O(d) | Only a constant number of candidates are generated, each requiring O(d) string work |
| Space | O(d) | Candidate strings and palindrome construction require linear space |
The algorithm generates only five to seven candidates regardless of the numeric value. Each palindrome construction involves string reversal operations proportional to the number of digits. Therefore the total runtime scales linearly with input length.
Since the input length is at most 18, the solution is extremely efficient.
Test Cases
solution = Solution()
assert solution.nearestPalindromic("123") == "121" # Basic example
assert solution.nearestPalindromic("1") == "0" # Single digit edge case
assert solution.nearestPalindromic("10") == "9" # Tie between 9 and 11
assert solution.nearestPalindromic("11") == "9" # Existing palindrome
assert solution.nearestPalindromic("99") == "101" # Larger digit count palindrome
assert solution.nearestPalindromic("100") == "99" # Tie with 101
assert solution.nearestPalindromic("1000") == "999" # Boundary reduction
assert solution.nearestPalindromic("999") == "1001" # Boundary expansion
assert solution.nearestPalindromic("1283") == "1331" # Even length case
assert solution.nearestPalindromic("12321") == "12221" # Odd length palindrome
assert solution.nearestPalindromic("808") == "818" # Existing palindrome
assert solution.nearestPalindromic("9999") == "10001" # Expansion edge
assert solution.nearestPalindromic("10001") == "9999" # Reduction edge
assert solution.nearestPalindromic("10987") == "11011" # Prefix increment case
assert solution.nearestPalindromic("54345") == "54245" # Prefix decrement case
Test Summary
| Test | Why |
|---|---|
"123" |
Standard non-palindrome example |
"1" |
Smallest valid input |
"10" |
Tie-breaking behavior |
"11" |
Existing palindrome |
"99" |
Requires larger digit palindrome |
"100" |
Boundary transition downward |
"1000" |
Power of ten edge case |
"999" |
All nines edge case |
"1283" |
Even length input |
"12321" |
Odd length palindrome |
"808" |
Palindrome with nearby candidates |
"9999" |
Expansion to longer palindrome |
"10001" |
Reduction to shorter palindrome |
"10987" |
Prefix increment generates answer |
"54345" |
Prefix decrement generates answer |
Edge Cases
Power of Ten Inputs
Numbers like "10", "100", and "1000" are particularly tricky because the nearest palindrome may have fewer digits.
For example:
"1000"has nearest palindromes999and1001- Both are distance 1
- The smaller one must be returned
A naive mirroring approach often misses 999. This implementation handles it by explicitly including:
$$10^{length-1} - 1$$
as a candidate.
All Nines Inputs
Numbers such as "9", "99", and "999" require transitioning to a larger digit count.
For example:
"999"→ nearest palindrome is1001
Simply mirroring the prefix cannot produce this result. The implementation solves this using the explicit boundary candidate:
$$10^{length} + 1$$
Input Already Being a Palindrome
When the original number is already a palindrome, it may appear in the candidate set.
For example:
"121"naturally generates candidate121
However, the problem explicitly says we cannot return the original number itself.
The implementation safely handles this using:
candidates.discard(original)
This guarantees the returned palindrome is different from the input.
Tie Situations
Some inputs have two equally close palindromes.
Example:
"1"→ candidates0and2- Both are distance 1
The problem requires returning the smaller palindrome in such cases.
The implementation carefully checks:
elif difference == best_difference and candidate < best:
This ensures ties are resolved correctly according to the specification.