564. Find the Closest Palindrome Solution

Q: Is Find the Closest Palindrome easy or hard?

Find the Closest Palindrome is classified as a Hard problem because of tricky edge cases and the need to avoid brute force. Handling digit-length transitions like 999 → 1001 or 1000 → 999 makes the implementation subtle. Once the prefix-mirroring insight is understood, the algorithm becomes manageable.

Q: Find the Closest Palindrome Python/Java solution

Most implementations follow the same pattern across Python, Java, C++, and JavaScript. Extract the first half of the string, create mirrored candidates using prefix, prefix+1, and prefix-1, and include edge cases like 999... and 100...001. Compare absolute differences and return the closest palindrome.

Q: How to solve Find the Closest Palindrome in O(n)?

Treat the number as a string and work with its prefix. Mirror the left half to form a palindrome, then also mirror prefix-1 and prefix+1. Add edge candidates like 10^d + 1 and 10^(d-1) - 1 to cover digit-length changes. Compare the absolute differences and pick the closest value not equal to the original number.

Q: What is the best approach for Find the Closest Palindrome?

The most efficient approach uses mirroring and prefix adjustment. Mirror the left half of the number to create a palindrome, then also generate candidates by incrementing and decrementing the prefix. Evaluate these few candidates and choose the one with the smallest difference from the original number. This reduces the search space dramatically and runs in O(d) time where d is the number of digits.

Q: Is Find the Closest Palindrome asked at Google/Amazon/Meta?

Palindrome and numeric string manipulation problems appear frequently in interviews at companies like Google, Amazon, and Meta. Variants of this question test understanding of edge cases, string handling, and mathematical reasoning. The optimized mirroring approach demonstrates strong problem-solving skills expected in senior interviews.

Q: What data structure is used in Find the Closest Palindrome?

The solution primarily uses string manipulation rather than complex data structures. The number is processed as a string to safely handle very large values. Candidate palindromes are generated by modifying and mirroring string prefixes, then compared using numeric difference calculations.

Q: What is the time complexity of Find the Closest Palindrome?

The optimal solution runs in O(d) time and O(d) space, where d is the number of digits in the input string. Only a constant number of palindrome candidates are generated by mirroring modified prefixes. Each candidate comparison and construction takes linear time with respect to the digit count.

The problem

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 <= 18
n consists of only digits.
n does not have leading zeros.
n is representing an integer in the range [1, 10¹⁸ - 1].

Approach overview

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.

Approach 1: Mirroring and Adjustment

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.

Python

def mirror_palindrome(s):
    return int(s[:len(s)//2] + s[:(len(s)+1)//2][::-1])


def closest_palindrome(n):
    length = len(n)
    original = int(n)
    best = float('inf')

    mirror_value = mirror_palindrome(n)

    candidates = {mirror_value}
    center = (length - 1) // 2

    lower = list(n)
    lower[center] = chr(ord(lower[center]) - 1)
    candidates.add(mirror_palindrome(''.join(lower)))

    higher = list(n)
    higher[center] = chr(ord(higher[center]) + 1)
    candidates.add(mirror_palindrome(''.join(higher)))

    for c in candidates:
        if c != original:
            if abs(c - original) < abs(best - original) or (abs(c - original) == abs(best - original) and c < best):
                best = c

    return str(best)

Java

public class ClosestPalindrome {
    private static long mirrorPalindrome(String str) {
        char[] chars = str.toCharArray();
        int n = chars.length;
        for (int i = 0; i < n / 2; i++) {
            chars[n - 1 - i] = chars[i];
        }
        return Long.parseLong(new String(chars));
    }
    
    public static String closestPalindrome(String n) {
        int len = n.length();
        long original = Long.parseLong(n);
        long best = Long.MAX_VALUE;
        String result = "";

        // Generate basic, lower and higher mirroring
        StringBuilder lower = new StringBuilder(n);
        StringBuilder higher = new StringBuilder(n);

        long mirrorValue = mirrorPalindrome(n);

        // Compare different mirroring options
        if (mirrorValue != original) best = mirrorValue;

        char lowerChar = lower.charAt((len-1)/2);
        lower.setCharAt((len-1)/2, lowerChar == '0' ? '9' : (char)(lowerChar - 1));
        long lowMirror = mirrorPalindrome(lower.toString());
        if (Math.abs(lowMirror - original) < Math.abs(best - original) || (Math.abs(lowMirror - original) == Math.abs(best - original) && lowMirror < best)) {
            best = lowMirror;
        }

        char higherChar = higher.charAt((len-1)/2);
        higher.setCharAt((len-1)/2, (char)(higherChar + 1));
        long highMirror = mirrorPalindrome(higher.toString());
        if (Math.abs(highMirror - original) < Math.abs(best - original) || (Math.abs(highMirror - original) == Math.abs(best - original) && highMirror < best)) {
            best = highMirror;
        }

        result = Long.toString(best);
        return result;
    }
}

C++

#include <iostream>
#include <string>
#include <cmath>
#include <climits>
using namespace std;

long long mirrorPalindrome(string str) {
    int n = str.size();
    for (int i = 0; i < n / 2; ++i) {
        str[n - 1 - i] = str[i];
    }
    return stoll(str);
}

string closestPalindrome(string n) {
    int len = n.size();
    long long original = stoll(n);
    long long best = LLONG_MAX;
    string result;

    // Generate basic, lower and higher mirroring
    string lower = n, higher = n;

    long long mirrorValue = mirrorPalindrome(n);

    // Compare different mirroring options
    if (mirrorValue != original) best = mirrorValue;
    
    lower[(len-1)/2] = lower[(len-1)/2] == '0' ? '9' : lower[(len-1)/2] - 1;
    long long lowMirror = mirrorPalindrome(lower);
    if (abs(lowMirror - original) < abs(best - original) || (abs(lowMirror - original) == abs(best - original) && lowMirror < best)) {
        best = lowMirror;
    }

    higher[(len-1)/2] = '0' + (higher[(len-1)/2] - '0' + 1) % 10;
    long long highMirror = mirrorPalindrome(higher);
    if (abs(highMirror - original) < abs(best - original) || (abs(highMirror - original) == abs(best - original) && highMirror < best)) {
        best = highMirror;
    }

    result = to_string(best);
    return result;
}

JavaScript

function mirrorPalindrome(s) {
    let n = s.length;
    let result = s.split('');
    for (let i = 0; i < Math.floor(n / 2); i++) {
        result[n - 1 - i] = s[i];
    }
    return parseInt(result.join(''));
}

function closestPalindrome(n) {
    let original = parseInt(n);
    let best = Number.MAX_SAFE_INTEGER;

    // Generate basic, lower and higher mirroring
    let lower = n.split('');
    let higher = n.split('');

    let mirrorValue = mirrorPalindrome(n);

    // Compare different mirroring options
    if (mirrorValue !== original) best = mirrorValue;

    lower[Math.floor((n.length-1)/2)] = String.fromCharCode(lower[Math.floor((n.length-1)/2)].charCodeAt(0) - 1);
    let lowMirror = mirrorPalindrome(lower.join(''));
    if (Math.abs(lowMirror - original) < Math.abs(best - original) || (Math.abs(lowMirror - original) === Math.abs(best - original) && lowMirror < best)) {
        best = lowMirror;
    }

    higher[Math.floor((n.length-1)/2)] = String.fromCharCode(higher[Math.floor((n.length-1)/2)].charCodeAt(0) + 1);
    let highMirror = mirrorPalindrome(higher.join(''));
    if (Math.abs(highMirror - original) < Math.abs(best - original) || (Math.abs(highMirror - original) === Math.abs(best - original) && highMirror < best)) {
        best = highMirror;
    }

    return best.toString();
}

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>

long long mirrorPalindrome(char *str) {
    int n = strlen(str);
    char result[n + 1];
    strcpy(result, str);
    for (int i = 0; i < n / 2; i++) {
        result[n - 1 - i] = str[i];
    }
    return atoll(result);
}

char *closestPalindrome(char *n) {
    int len = strlen(n);
    long long original = atoll(n);
    long long best = LLONG_MAX;
    char *result = (char *)malloc(len + 2);

    // Generate basic, lower and higher mirroring
    char lower[len + 1], higher[len + 1];
    strcpy(lower, n);
    strcpy(higher, n);

    long long mirrorValue = mirrorPalindrome(n);

    // Compare different mirroring options
    if (mirrorValue != original) best = mirrorValue;
    
    lower[(len-1)/2]--; // Decrement the middle (or left middle)
    long long lowMirror = mirrorPalindrome(lower);
    if (abs(lowMirror - original) < abs(best - original) || (abs(lowMirror - original) == abs(best - original) && lowMirror < best)) {
        best = lowMirror;
    }

    higher[(len-1)/2]++; // Increment the middle (or left middle)
    long long highMirror = mirrorPalindrome(higher);
    if (abs(highMirror - original) < abs(best - original) || (abs(highMirror - original) == abs(best - original) && highMirror < best)) {
        best = highMirror;
    }

    sprintf(result, "%lld", best);
    return result;
}

using System;

public class ClosestPalindrome {
    private static long MirrorPalindrome(string str) {
        char[] chars = str.ToCharArray();
        int n = chars.Length;
        for (int i = 0; i < n / 2; i++) {
            chars[n - 1 - i] = chars[i];
        }
        return long.Parse(new string(chars));
    }

    public static string Closest(string n) {
        int len = n.Length;
        long original = long.Parse(n);
        long best = long.MaxValue;
        string result = "";

        // Generate basic, lower and higher mirroring
        char[] lower = n.ToCharArray();
        char[] higher = n.ToCharArray();

        long mirrorValue = MirrorPalindrome(n);

        // Compare different mirroring options
        if (mirrorValue != original) best = mirrorValue;

        lower[(len-1)/2]--;
        long lowMirror = MirrorPalindrome(new string(lower));
        if (Math.Abs(lowMirror - original) < Math.Abs(best - original) || (Math.Abs(lowMirror - original) == Math.Abs(best - original) && lowMirror < best)) {
            best = lowMirror;
        }

        higher[(len-1)/2]++;
        long highMirror = MirrorPalindrome(new string(higher));
        if (Math.Abs(highMirror - original) < Math.Abs(best - original) || (Math.Abs(highMirror - original) == Math.Abs(best - original) && highMirror < best)) {
            best = highMirror;
        }

        result = best.ToString();
        return result;
    }
}

The Python solution uses slicing and string reversal to quickly generate mirrored candidates. It loops through potential candidates and updates based on distance criteria, efficiently generating options through array manipulation and comparisons.

Complexity

Time Complexity: O(n) because generating and comparing different mirrored versions involve handling each character.
Space Complexity: O(n) requires storage of string elements and potential candidates.

Try this approach in the editor

Approach 2: Default Approach

func nearestPalindromic(n string) string {
	l := len(n)
	res := []int{int(math.Pow10(l-1)) - 1, int(math.Pow10(l)) + 1}
	left, _ := strconv.Atoi(n[:(l+1)/2])
	for _, x := range []int{left - 1, left, left + 1} {
		y := x
		if l&1 == 1 {
			y /= 10
		}
		for ; y > 0; y /= 10 {
			x = x*10 + y%10
		}
		res = append(res, x)
	}
	ans := -1
	x, _ := strconv.Atoi(n)
	for _, t := range res {
		if t != x {
			if ans == -1 || abs(t-x) < abs(ans-x) || abs(t-x) == abs(ans-x) && t < ans {
				ans = t
			}
		}
	}
	return strconv.Itoa(ans)
}

func abs(x int) int {
	if x < 0 {
		return -x
	}
	return x
}

Try this approach in the editor

Complexity comparison

Approach	Complexity
Mirroring and Adjustment	Time Complexity: O(n) because generating and comparing different mirrored versions involve handling each character. Space Complexity: O(n) requires storage of string elements and potential candidates.
Default Approach	–

Complexity analysis

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

Frequently asked questions

Is Find the Closest Palindrome easy or hard?

Find the Closest Palindrome is classified as a Hard problem because of tricky edge cases and the need to avoid brute force. Handling digit-length transitions like 999 → 1001 or 1000 → 999 makes the implementation subtle. Once the prefix-mirroring insight is understood, the algorithm becomes manageable.

Find the Closest Palindrome Python/Java solution

Most implementations follow the same pattern across Python, Java, C++, and JavaScript. Extract the first half of the string, create mirrored candidates using prefix, prefix+1, and prefix-1, and include edge cases like 999... and 100...001. Compare absolute differences and return the closest palindrome.

How to solve Find the Closest Palindrome in O(n)?

Treat the number as a string and work with its prefix. Mirror the left half to form a palindrome, then also mirror prefix-1 and prefix+1. Add edge candidates like 10^d + 1 and 10^(d-1) - 1 to cover digit-length changes. Compare the absolute differences and pick the closest value not equal to the original number.

What is the best approach for Find the Closest Palindrome?

The most efficient approach uses mirroring and prefix adjustment. Mirror the left half of the number to create a palindrome, then also generate candidates by incrementing and decrementing the prefix. Evaluate these few candidates and choose the one with the smallest difference from the original number. This reduces the search space dramatically and runs in O(d) time where d is the number of digits.

Is Find the Closest Palindrome asked at Google/Amazon/Meta?

Palindrome and numeric string manipulation problems appear frequently in interviews at companies like Google, Amazon, and Meta. Variants of this question test understanding of edge cases, string handling, and mathematical reasoning. The optimized mirroring approach demonstrates strong problem-solving skills expected in senior interviews.

What data structure is used in Find the Closest Palindrome?

The solution primarily uses string manipulation rather than complex data structures. The number is processed as a string to safely handle very large values. Candidate palindromes are generated by modifying and mirroring string prefixes, then compared using numeric difference calculations.

What is the time complexity of Find the Closest Palindrome?

The optimal solution runs in O(d) time and O(d) space, where d is the number of digits in the input string. Only a constant number of palindrome candidates are generated by mirroring modified prefixes. Each candidate comparison and construction takes linear time with respect to the digit count.

Find the Closest Palindrome solution and explanation

The problem

Approach overview

Approach 1: Mirroring and Adjustment

Approach 2: Default Approach

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Find the Closest Palindrome solution and explanation

The problem

Approach overview

Approach 1: Mirroring and Adjustment

Approach 2: Default Approach

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Related problems