HardMathStringUpdated Sep 2026

564. Find the Closest Palindrome

Asked at Uber

Difficulty

Hard

Time

O(L)

Space

O(L)

Pattern

Math

Companies

1

Problem

You are given a string n that holds a positive integer written in decimal, with no leading zeros. Return the closest palindrome to that number, as a string.

"Closest" means the smallest absolute difference. The number n itself is not allowed as an answer, even if it is already a palindrome — you must return a different number. If two palindromes are equally close (one below, one above), return the smaller one.

The answer may have fewer digits or more digits than n. For example, the closest palindrome to 1001 is 999, and the closest palindrome to 999 is 1001.

Find the nearest palindrome

palindromes near 123111121131012121 is only 2 away, closer than 111 (12 away) and 131(8 away)n itself is never allowedtie → return the smaller palindrome
For n = 123 we look at palindromes on both sides and pick the one with the smallest distance.

Constraints

  • ●1 <= n.length <= 18
  • ●n consists of only digits
  • ●n does not have leading zeros
  • ●n represents an integer in the range [1, 10^18 - 1]

Examples

Example 1
Inputn = "123"
Output"121"
Why121 is a palindrome and differs from 123 by 2. The next options 131 (diff 8) and 111 (diff 12) are farther, so 121 wins.
Example 2
Inputn = "1"
Output"0"
Why0 and 2 are both palindromes at distance 1 from 1. The tie is broken by taking the smaller value, so the answer is 0.

Asked At

1 companies
CompanyDifficulty
UberHardView all Uber questions →

How to Think About It

1

Brute force: check n-1, n-2, ... and n+1, n+2, ... until a palindrome is found — too slow for large n.

2

Key insight: the closest palindrome has the same number of digits or one fewer/more, and is constructed by mirroring the first half.

3

Generate candidates by mirroring: mirror(n), mirror(n-1), mirror(n+1), mirror(n-99...9), mirror(n+100...0).

4

Also consider edge cases: 10...01 mirrors to 9...9 (one fewer digit), 99...9 mirrors to 100...001 (one more digit).

5

At most 9 candidates to check — compare each against n and return the closest, breaking ties by choosing the smaller.

Optimal Approach

Generate up to 9 candidate palindromes by considering mirroring the prefix of n (the first half). Take the prefix as the first ceil(len/2) digits, mirror it to form a palindrome, and also generate palindromes from prefix-1 and prefix+1 to handle cases where the closest palindrome differs in the middle digits. Additionally handle boundary cases like 10...01 (returns 9...9) and 9...9 (returns 10...01). Compare all candidates (excluding n itself) and return the closest, breaking ties by choosing the smaller value. This runs in O(1) since the number of digits is bounded.

Mirror the prefix

n = 123prefix = 12123012Step 1 — take the first ceil(3/2) = 2 digits as theprefixmirror prefix 12121012Step 2 — mirror the prefix: 12 → 121, a palindromecandidates11112113199100101234Step 3 — also try prefix−1, prefix+1, all 9s, and 1…1;drop n itselfbest = min |c − n|tie → smaller valueanswer = 121
Take the first half of n, mirror it, and also try prefix−1 and prefix+1 to cover the middle digits.
ComplexityTime O(L)Space O(L)L is the number of digits (at most 18). We only build and compare a constant number of candidates, so the work is linear in the digit count.

What Trips People Up in Real Interviews

1

Clarify that n itself is never the answer (must return a different palindrome).

2

Edge cases: n=1 returns "0" (closest palindrome), n=2 returns "1".

3

The candidate generation must handle carry/borrow when incrementing/decrementing the prefix.

4

Use string comparison for large numbers since n can be up to 18 digits (exceeds 64-bit).

5

Tie-breaking: if two candidates are equidistant, return the smaller one.

Solution Code

O(L) time
def nearestPalindromic(n):
    length = len(n)
    if length == 1:
        return str(int(n) - 1)
    candidates = set()
    prefix = int(n[:(length + 1) // 2])
    for p in [prefix - 1, prefix, prefix + 1]:
        s = str(p)
        if length % 2 == 0:
            candidate = s + s[::-1]
        else:
            candidate = s + s[:-1][::-1]
        candidates.add(candidate)
    candidates.add('9' * (length - 1))
    candidates.add('1' + '0' * (length - 1) + '1')
    candidates.discard(n)
    best = None
    n_int = int(n)
    for c in candidates:
        diff = abs(int(c) - n_int)
        if best is None or diff < abs(int(best) - n_int) or (diff == abs(int(best) - n_int) and int(c) < int(best)):
            best = c
    return best

Pro at DSA?

Test your skills with a real FAANG-style mock interview.

Start a Mock Interview →

Frequently Asked Questions

What is the Find the Closest Palindrome problem?

Given a string n representing an integer, return the closest palindrome (not including itself) to n. If there is a tie, return the smaller one. The input n is a string of length 1 to 18 digits and will not have leading zeros.

How do you solve Find the Closest Palindrome?

The optimal approach runs in O(L) time and O(L) space. Scroll up to "Optimal Approach" for the step-by-step walkthrough, diagrams, and code in Python, C++ and Java.

What companies ask Find the Closest Palindrome?

Find the Closest Palindrome is asked at Uber. It is a hard difficulty problem.

What are common mistakes on Find the Closest Palindrome?
  • Clarify that n itself is never the answer (must return a different palindrome).
  • Edge cases: n=1 returns "0" (closest palindrome), n=2 returns "1".
  • The candidate generation must handle carry/borrow when incrementing/decrementing the prefix.
  • Use string comparison for large numbers since n can be up to 18 digits (exceeds 64-bit).
  • Tie-breaking: if two candidates are equidistant, return the smaller one.