LeetCode 564: Find the Closest Palindrome (Explained, With Video)

The problem: given an integer as a string n, return the closest integer palindrome that is not n itself. If two palindromes are equally close, return the smaller one.

Brute force (walk outward from n checking each number) is far too slow, since n can have 18 digits. The trick is that the answer is always one of just five candidates.

The five candidates

1. Mirror the first half. Keep the left half (including the middle digit for odd lengths) and copy it onto the right: 12932 -> 12921.
2. First half plus one, mirrored: 12932 -> 130 -> 13031.
3. First half minus one, mirrored: 12932 -> 128 -> 12821.
4. All nines with one fewer digit: 10^(L-1) - 1, for example 1000 -> 999.
5. One, zeros, one with one more digit: 10^L + 1, for example 99 -> 101.

Candidates 4 and 5 cover the cases where changing the half crosses a power of ten. Drop n itself from the set, then pick the candidate with the smallest absolute difference, breaking ties by the smaller value.

Python solution

def nearestPalindromic(n: str) -> str:
    L, num = len(n), int(n)
    candidates = {10 ** (L - 1) - 1, 10 ** L + 1}
    prefix = int(n[:(L + 1) // 2])
    for p in (prefix - 1, prefix, prefix + 1):
        s = str(p)
        pal = s + s[::-1] if L % 2 == 0 else s + s[-2::-1]
        candidates.add(int(pal))
    candidates.discard(num)
    return str(min(candidates, key=lambda x: (abs(x - num), x)))

It runs in O(L) time for L digits. Python integers handle the 18-digit inputs; in Java or C++ use long.

Edge cases to test

Video walkthrough

This problem was worked live in an SDE Skills daily coding session (10,000+ views).

Practice problems like this with others, free

SDE Skills is a volunteer-run 501(c)(3) nonprofit with free daily LeetCode practice on Zoom. See the schedule, the LeetCode practice guide and the free DSA practice sheet.

Join a session on Zoom Join our free Discord