Abstract / Summary

Given a number represented as a string and an integer k, find the closest number that is a palindrome and at most k away from the given number.

Note

The full problem description, including helpful examples, can be found on LeetCode.

This problem is ranked as

and has an acceptance rate of about 32% (400k+ submissions).

Typical patterns to solve this problem:

• Math
• String

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.

Overview

The provided implementation defines a class Solution with a method nearestPalindromic that receives a numeric string n and returns the closest palindrome number (as a string) that is different from n. The algorithm builds a small set of candidate palindromes around the input, then selects the one with the smallest absolute distance to the original value.

Key Steps

The method begins by determining the length of the input string.

size = len(n)

If the input consists of a single digit, the only possible smaller palindrome is the preceding integer, which is returned directly.

if size == 1:
    return str(int(n) - 1)

Two baseline candidates are generated: the largest palindrome with one fewer digit (all 9's) and the smallest palindrome with one more digit (a 1 followed by zeros and ending with 1).

candidates = [ "9" * (size - 1) ]          # e.g., 999 for a 4-digit input
candidates.append("1" + "0" * (size - 1) + "1")

The algorithm then prepares to create palindromes that share the same length as the input. It computes the length of the left half (including the middle digit for odd lengths) and records whether the length is odd.

half = (size + 1) // 2
odd  = size % 2 == 1

The numeric value of the left half of the original number is extracted.

first = int(n[:half])

A loop iterates over three values: one less than, equal to, and one greater than this left half. For each iteration, a candidate palindrome is constructed by mirroring the appropriate portion of the left half.

for i in range(first - 1, first + 2):
    one  = str(i)
    two  = one[:-1] if odd else one
    two  = two[::-1]
    if one + two != n:
        candidates.append(one + two)

After all candidates are collected, they are sorted according to their absolute distance from the original number, and the first element (the closest palindrome) is returned.

candidates.sort(key = lambda x : abs(int(x) - int(n)))
return candidates[0]

Edge Cases Handled

When the input consists of a single digit, the method bypasses the general palindrome construction and directly returns the preceding integer, ensuring a valid palindrome result for inputs like "0" or "5".

The candidate "9" * (size - 1) addresses the situation where the nearest palindrome has fewer digits than the input, such as turning "1000" into "999".

The candidate "1" + "0" * (size - 1) + "1" covers the case where the nearest palindrome has more digits, for example converting "999" to "1001".

During the loop that varies the left half, the condition if one + two != n guarantees that the original number itself is never returned, even when it is already a palindrome. This prevents the algorithm from mistakenly selecting the input as the nearest palindrome.

The handling of odd and even lengths via the odd flag ensures that the middle digit is not duplicated when mirroring, preserving correct palindrome structure for both cases (e.g., "12321" versus "1221").

Performance Optimizations

String multiplication ("9" * (size - 1) and "0" * (size - 1)) creates the baseline candidates in a single operation, avoiding iterative concatenation.

Extracting the left half once (first = int(n[:half])) and reusing it for the three nearby values reduces repeated slicing and conversion overhead.

The loop iterates only three times, regardless of the input size, which keeps the candidate generation phase constant in terms of iteration count.

Sorting the candidate list uses a custom key that computes the absolute difference on demand, allowing Python’s highly optimized Timsort to efficiently order a very small list (typically five elements). This approach avoids manual comparison logic and leverages built-in sorting performance.

Imagine you are holding a secret number, and you want to find the nearest number that reads exactly the same forwards and backwards, just like a mirror. This code acts like a tiny detective tasked with finding that special match.

First, the detective checks how long the number is. If the number is very small like a single finger, it just takes one away to find the answer.

If the number is bigger, the detective starts brainstorming a list of possibilities. It looks at numbers made of lots of nines, or special numbers that start and end with one and have zeros in the middle. These are like classic mirror shapes.

Then, the detective looks closely at the first part of your secret number. It takes that part and tries changing it just a little bit, either by making it slightly smaller, keeping it the same, or making it slightly bigger. It carefully flips those new pieces around to create new mirror numbers and adds them to the collection of possibilities.

Finally, the detective compares all the numbers in the collection to see which one is the closest neighbor to the original number. It ignores any that match the original perfectly and picks the one that is the closest distance away.

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):

Time: linear
As a rule of thumb, the maximum input size for one second execution time is

• factorial: up to 10 elements
• exponential: up to 20 elements
• polynomial: a few thousand elements
• loglinear: up to 100,000 elements
• linear: a few million elements
• logarithmic: a billion elements
• constant: practically unlimited

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)

	author
author	solutions
www	AlgoMonster	C++		Java		Python			TS
	WalkCCC	C++		Java		Python
	leetcode.ca	C++	JS	Java		Python		Go
	LeetcodeHelp	C++		Java		Python
	Progiez	C++		Java		Python
github	black-shadows	C++
	charles-wangkai			Java
	everthis		JS
	gouthampradhan			Java
	JoshCrozier		JS
	keineahnung2345	C++
	linouk23					Python
	ruoru				Rust
	suxrobGM						C#
	wisdompeak	C++
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, Go, Java, JavaScript, Python
LeetcodeHelp	C++, Java, Python
Progiez	C++, Java, Python
black-shadows	C++, C++
charles-wangkai	Java
everthis	JavaScript
gouthampradhan	Java
JoshCrozier	JavaScript
keineahnung2345	C++
linouk23	Python
ruoru	Rust
suxrobGM	C#
wisdompeak	C++

There are a few extra pages giving you some insights into my setup:

• Tech Stack - my development environment and tools
• AI - how AI helped me create this website (NOT solving the problems)
• Progress - progression over time
• Quality - code quality