Given a string n representing an integer, return the closest integer (not including itself), which is a palindrome. If there is a tie, return the smaller one.
The closest is defined as the absolute difference minimized between two integers.
Example 1:
Input: n = "123" Output: "121"
Example 2:
Input: n = "1" Output: "0" Explanation: 0 and 2 are the closest palindromes but we return the smallest which is 0.
Constraints:
1 <= n.length <= 18n consists of only digits.n does not have leading zeros.n is representing an integer in the range [1, 1018 - 1].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.
This approach involves mirroring the first half of the number to form the second half which can create a potential palindrome. After forming the basic mirrored palindrome, consider the numbers formed by adjusting the half upwards and downwards. This will cover all possible close numbers. Finally, choose the closest and smallest palindrome by comparing all options.
The C language solution creates a helper function to generate a mirrored palindrome given a string. It then creates potential palindrome candidates by mirroring the number, decrementing, and incrementing the middle digit(s). The closest candidate by absolute difference is selected as the solution.
Time Complexity: O(n) where n is the length of the string, as it involves mirroring which is a linear operation.
Space Complexity: O(n) for storing temporary palindrome strings.
Python
Java
C++
Go
JavaScript
| Approach | Complexity |
|---|---|
| Mirroring and Adjustment | Time Complexity: O(n) where n is the length of the string, as it involves mirroring which is a linear operation. |
| Default Approach | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Increment/Decrement Search | O(k * d) | O(1) | Conceptual baseline or very small inputs where search distance is minimal |
| Mirroring and Prefix Adjustment | O(d) | O(d) | Optimal solution for large numeric strings and expected interview approach |
Find the Closest Palindrome | Simple Observations | Leetcode 564 | codestorywithMIK • codestorywithMIK • 13,894 views views
Watch 9 more video solutions →Practice Find the Closest Palindrome with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor