Limited Time Offer:Up to 25% off Hello Interview Premium

⌘K

Tutor

Get Premium

Leetcode 564. Find the Closest Palindrome

Given a numeric string n (up to 18 digits), find the closest integer palindrome different from n (ties broken by smaller value). The typical approach is to generate candidate palindromes by adjusting and mirroring the prefix and including boundary cases (e.g., 10^k±1, all 9s), then pick the candidate with minimal absolute difference.

Asked at:

Uber

DESCRIPTION

Input:

n = "123"

Output:

"121"

Explanation: The closest palindrome to 123 is 121, with a distance of 2. Other palindromes like 111 (distance 12) or 131 (distance 8) are farther away.

Constraints:

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

Understanding the Problem

Let's understand what we're being asked to do. We have a numeric string n like '123' and need to find the closest palindrome that is different from n.

For example, if n = '123', some palindromes near it are '121' (distance 2), '131' (distance 8), '111' (distance 12). The closest is '121'.

Important constraint: The palindrome must be different from n itself. So if n = '121' (already a palindrome), we can't return '121' - we need the next closest like '111' or '131'.

Key insight: We need to consider multiple candidate palindromes: mirroring the prefix, incrementing/decrementing the middle, and boundary cases like 999...999 or 100...001.

Edge cases to consider: What if n = '1'? (return '0'). What if n = '99'? (return '101', crossing a power-of-10 boundary). What if there's a tie in distance? (return the smaller palindrome).

Building Intuition

A palindrome is determined entirely by its first half - the second half is just a mirror. For n = '12345', if we take the first half '123' and mirror it, we get '12321'.

But this mirrored palindrome might not be the closest! We also need to consider what happens if we increment or decrement the middle part before mirroring.

By adjusting the prefix (the part that determines the palindrome) up or down by 1, we generate nearby palindrome candidates. For n = '12345', candidates include: mirroring '123' → '12321', mirroring '124' → '12421', mirroring '122' → '12221'.

We also need boundary cases: numbers like '999' (next palindrome is '1001') or '1000' (previous palindrome is '999'). These cross power-of-10 boundaries.

Think of a palindrome as a folded piece of paper - what you write on one side appears on the other. The challenge is finding which 'fold point' (prefix) gives us the closest result.

Imagine n = '1234'. We can try folding at different points: '12|34' → mirror to get '1221', or adjust the left side first: '13|34' → '1331', or '11|34' → '1111'. We generate all reasonable candidates and pick the closest.

Don't forget edge cases: '9999' can't just increment the middle - it needs to become '10001' (one digit longer!).

Common Mistakes

Forgetting to exclude n itself: if n is already a palindrome, the mirrored version equals n, which is invalid. Must generate other candidates.

Missing boundary cases: failing to consider 999...999 (decrement to get 100...001) or 100...001 (increment to get 999...999) leads to incorrect results for edge inputs.

Incorrect tie-breaking: when two palindromes have the same distance, must return the smaller one. Forgetting this rule causes wrong answers on tied cases.

Integer overflow: using 64-bit integers fails for n with 18 digits. Must use string-based arithmetic or big integer libraries.

Off-by-one errors in prefix extraction: incorrectly determining which digits form the prefix (especially for odd vs even length strings) leads to wrong mirrored palindromes.

Optimal Solution

Generate candidate palindromes by: (1) mirroring the prefix of n, (2) incrementing the prefix and mirroring, (3) decrementing the prefix and mirroring, and (4) including boundary cases like 10^k - 1 (all 9s) and 10^k + 1 (100...001). For each candidate, compute the absolute difference from n. Select the candidate with the smallest difference, breaking ties by choosing the smaller value. This approach systematically covers all nearby palindromes without exhaustive search.

Visualization

def nearest_palindrome(n):
    """
    Find the closest palindrome to n (different from n).
    Ties broken by smaller value.
    """
    length = len(n)
    num = int(n)
    candidates = []
    
    # Boundary cases: 999...999 (length-1) and 100...001 (length+1)
    candidates.append(10**length + 1)  # 100...001
    candidates.append(10**(length - 1) - 1)  # 999...999
    
    # Get prefix (first half, including middle for odd length)
    prefix_len = (length + 1) // 2
    prefix = int(n[:prefix_len])
    
    # Generate candidates by mirroring prefix-1, prefix, prefix+1
    for delta in [-1, 0, 1]:
        new_prefix = str(prefix + delta)
        
        # Mirror the prefix to create palindrome
        if length % 2 == 0:
            # Even length: mirror entire prefix
            candidate = new_prefix + new_prefix[::-1]
        else:
            # Odd length: mirror all but middle character
            candidate = new_prefix + new_prefix[-2::-1]
        
        candidates.append(int(candidate))
    
    # Find closest palindrome different from n
    best = -1
    min_diff = float('inf')
    
    for cand in candidates:
        # Skip if same as n
        if cand == num:
            continue
        
        diff = abs(cand - num)
        
        # Update if closer, or same distance but smaller
        if diff < min_diff or (diff == min_diff and cand < best):
            min_diff = diff
            best = cand
    
    return str(best)

Find closest palindrome to 123

0 / 32

Test Your Knowledge

Complexity Analysis

Time Complexity: O(L) We generate a constant number of candidates (5-6 candidates), and for each candidate we perform string operations that take O(L) time where L is the length of n. Comparing candidates and finding the minimum also takes O(L) time.

Space Complexity: O(L) We store a constant number of candidate palindrome strings, each of length O(L). The total space is O(L) for storing these candidates and intermediate results.

What We've Learned

Candidate generation strategy: For palindrome problems with numeric constraints, generate a small set of strategic candidates rather than checking all possibilities - mirror the prefix to create base palindromes, then add boundary cases (999...999 and 100...001) which are often closest to numbers near powers of 10.
Prefix mirroring technique: To generate palindrome candidates, take the first half (including middle for odd length) of the number, try incrementing/decrementing it by 1, then mirror it to the second half - this creates the three most likely candidates while maintaining palindrome structure efficiently.
Edge case enumeration: Always include 10^k - 1 (all 9s) and 10^k + 1 (100...001) as candidates because numbers near power-of-10 boundaries often have their closest palindrome at these special values (e.g., 1000 → 999, 99 → 101), which aren't generated by simple mirroring.
String-based arithmetic for large numbers: When dealing with numbers up to 18 digits that exceed standard integer limits, use string manipulation for comparisons and adjustments rather than converting to long/int - this prevents overflow and maintains precision throughout the algorithm.
Tie-breaking with comparison logic: When two candidates have equal distance, implement explicit smaller-value selection by comparing absolute differences first, then choosing the numerically smaller candidate - don't rely on iteration order as it may not guarantee correct tie-breaking.
Self-exclusion validation: Always filter out the original number from candidates before selecting the closest - a common bug is returning the input itself when it's already a palindrome, violating the "different from n" requirement.

Test Your Understanding

Why is string the right data structure for this problem?

string provides the optimal access pattern

It's the only data structure that works

It's the easiest to implement

It uses the least memory

Select an answer to see the explanation

Question Timeline

See when this question was last asked and where, including any notes left by other candidates.

Company

Level

Region

Mid October, 2025

Uber

Senior

Mid August, 2025

Uber

Mid-level

Late July, 2025

Uber

Mid-level

Get Premium to View All 6 Reports

Comments

Your account is free and you can post anonymously if you choose.

Hello Interview Premium

Recent interview questions

System Design Guided Practice

Exclusive content

Learn More

Leetcode 564. Find the Closest Palindrome

DESCRIPTION

Understanding the Problem

Building Intuition

Common Mistakes

Optimal Solution

Test Your Knowledge

Complexity Analysis

What We've Learned

Related Concepts and Problems to Practice

Test Your Understanding

Question Timeline

Comments

Questions

Learn

Links

Legal

Contact