Find the Closest Palindrome - Solution & Explanation

Problem Overview: You are given a numeric string n. Return the closest integer (not equal to n) that forms a palindrome. If two palindromes are equally close, return the smaller one.

The challenge is the size of the number. The input can exceed standard integer limits, so operations must be performed using string manipulation and careful math reasoning. The key observation: the nearest palindrome will almost always share the same prefix as the original number or a small variation of it.

Approach 1: Brute Force Search (Potentially O(k * d) time, O(1) space)

One straightforward strategy is to increment and decrement from the given number until a palindrome appears. For each candidate number, convert it to a string and check if it reads the same forward and backward. This requires repeatedly performing palindrome checks on numbers with d digits.

The issue is the search distance k can grow large before hitting a palindrome, especially for inputs like 1000...0. While each check costs O(d), the number of checks is unpredictable. This approach demonstrates the core idea but fails for large inputs because the search space can become huge.

Approach 2: Mirroring and Prefix Adjustment (O(d) time, O(d) space)

The optimal strategy builds a small set of candidate palindromes instead of searching the entire number line. Start by mirroring the left half of the number onto the right half. For example, 12345 becomes 12321. This often produces the closest palindrome directly.

However, the nearest palindrome might require adjusting the prefix. Extract the first half of the number, then generate three variations: keep the prefix unchanged, increment it by one, and decrement it by one. Mirror each version to form full palindromes. This captures cases like 12932 → 13031 or 1000 → 999.

Edge cases appear when the number length changes, such as 999 → 1001 or 1000 → 999. Handle these by also considering boundary candidates like 10^d + 1 and 10^{d-1} - 1. After generating all candidates, compute the absolute difference from the original number and choose the smallest difference, breaking ties with the smaller value.

This approach works because only a handful of palindromes can possibly be closest. Instead of scanning millions of numbers, you evaluate about five candidates. Each candidate construction and comparison takes O(d) time where d is the digit count.

Recommended for interviews: Interviewers expect the mirroring and prefix adjustment technique. Brute force shows basic reasoning about palindromes, but the optimized solution demonstrates control over string manipulation, boundary cases, and numeric reasoning. Generating candidate palindromes directly reduces the complexity to linear time relative to the digit length.