LeetCode 564: Find the Closest Palindrome

Problem Restatement

We are given a string n representing an integer.

Return the closest integer palindrome to n.

The returned palindrome must not be n itself.

If there are two palindromes with the same distance from n, return the smaller one.

The input length is at most 18, so the number can be too large for some fixed-width integer languages, but Python can handle it directly. The official constraints say 1 <= n.length <= 18, n contains only digits, has no leading zeros, and represents an integer in [1, 10^18 - 1].

Input and Output

Example function shape:

def nearestPalindromic(n: str) -> str:
    ...

Examples

Example 1:

n = "123"

Nearby palindromes include:

The closest is:

"121"

Example 2:

n = "1"

The closest palindromes are:

There is a tie, so we return the smaller one:

"0"

Example 3:

n = "1000"

Nearby palindromes include:

"999"
"1001"

Both are close, but:

abs(1000 - 999) = 1
abs(1000 - 1001) = 1

Tie goes to the smaller palindrome, so the answer is:

"999"

First Thought: Search Outward

A direct idea is to check:

n - 1
n + 1
n - 2
n + 2
...

and stop when we find a palindrome.

This is simple, but it can be far too slow.

For a number like:

"100000000000000000"

we do not want to test many numbers one by one.

We need to construct only the palindromes that can be closest.

Key Insight

A nearby palindrome is determined mostly by the left half of the number.

For example:

n = "12345"

If we mirror the left half, we get:

"12321"

This is often the closest candidate.

But sometimes we need to adjust the prefix by -1 or +1.

For "12345", the relevant prefixes are:

122
123
124

Mirroring them gives:

12221
12321
12421

The closest palindrome must be among these prefix-based candidates, plus boundary cases.

Boundary Cases

Prefix mirroring alone does not handle changes in digit length.

For example:

So we always include:

10^(length - 1) - 1

This is the largest palindrome with one fewer digit, such as 999.

We also include:

10^length + 1

This is the smallest palindrome with one more digit, such as 1001.

Candidate Generation

Let:

length = len(n)
prefix_length = (length + 1) // 2
prefix = int(n[:prefix_length])

Then build candidates from:

prefix - 1
prefix
prefix + 1

For each prefix candidate, mirror it into a palindrome of the same length style.

If the original length is even, mirror the full prefix:

prefix = "12"
palindrome = "1221"

If the original length is odd, do not duplicate the middle digit:

prefix = "123"
palindrome = "12321"

Algorithm

1. Convert n to integer original.
2. Let length = len(n).
3. Add boundary candidates:

   10 ** (length - 1) - 1
   10 ** length + 1
4. Extract the left prefix of length (length + 1) // 2.
5. For prefix - 1, prefix, and prefix + 1:
   1. Mirror the prefix into a palindrome.
   2. Add it to the candidate set.
6. Remove original from candidates if present.
7. Choose the candidate with the smallest pair:

   (abs(candidate - original), candidate)
8. Return it as a string.

The pair comparison handles the tie rule automatically. Smaller distance wins first. If distances tie, smaller candidate wins.

Correctness

Any palindrome with the same number of digits is determined by its left half. To be close to n, its left half must be close to the left half of n.

If the left half differs by more than 1, the resulting palindrome changes a more significant part of the number too much. A closer or equal candidate can be obtained by using prefix - 1, prefix, or prefix + 1.

These three mirrored candidates cover the closest same-length palindromes around n.

However, the nearest palindrome may also have one fewer digit or one more digit. This happens near powers of ten and all-nine numbers. The candidates 10^(length - 1) - 1 and 10^length + 1 cover those cases.

The algorithm checks all relevant candidates, excludes n itself, and chooses the one with minimum absolute difference. If two candidates have the same difference, it chooses the smaller value. Therefore, it returns exactly the required closest palindrome.

Complexity

Let d = len(n).

The number of candidates is constant.

Implementation

class Solution:
    def nearestPalindromic(self, n: str) -> str:
        original = int(n)
        length = len(n)

        candidates = {
            10 ** (length - 1) - 1,
            10 ** length + 1,
        }

        prefix_length = (length + 1) // 2
        prefix = int(n[:prefix_length])

        for value in (prefix - 1, prefix, prefix + 1):
            left = str(value)

            if length % 2 == 0:
                palindrome = left + left[::-1]
            else:
                palindrome = left + left[-2::-1]

            candidates.add(int(palindrome))

        candidates.discard(original)

        best = min(candidates, key=lambda x: (abs(x - original), x))
        return str(best)

Code Explanation

We first store the original number as an integer:

original = int(n)

Then we add the two digit-length boundary candidates:

candidates = {
    10 ** (length - 1) - 1,
    10 ** length + 1,
}

For a length of 4, these are:

999
10001

Then we take the left half, including the middle digit for odd lengths:

prefix_length = (length + 1) // 2
prefix = int(n[:prefix_length])

For example:

We try the prefix itself and its neighbors:

for value in (prefix - 1, prefix, prefix + 1):

For even length, we mirror the full prefix:

palindrome = left + left[::-1]

For odd length, we skip duplicating the middle digit:

palindrome = left + left[-2::-1]

Then we remove the input number itself:

candidates.discard(original)

Finally, we choose by distance first, then value:

best = min(candidates, key=lambda x: (abs(x - original), x))

Testing

def run_tests():
    s = Solution()

    assert s.nearestPalindromic("123") == "121"
    assert s.nearestPalindromic("1") == "0"
    assert s.nearestPalindromic("10") == "9"
    assert s.nearestPalindromic("11") == "9"
    assert s.nearestPalindromic("99") == "101"
    assert s.nearestPalindromic("1000") == "999"
    assert s.nearestPalindromic("999") == "1001"
    assert s.nearestPalindromic("121") == "111"
    assert s.nearestPalindromic("1283") == "1331"

    print("all tests passed")

run_tests()