Skip to main content
Talentd

Find Palindrome With Fixed Length - Solution & Explanation

MediumArrayMath8 min readAsked at: VMware
Practice this problem

Problem Statement

Given an integer array queries and a positive integer intLength, return an array answer where answer[i] is either the queries[i]th smallest positive palindrome of length intLength or -1 if no such palindrome exists.

A palindrome is a number that reads the same backwards and forwards. Palindromes cannot have leading zeros.

 

Example 1:

Input: queries = [1,2,3,4,5,90], intLength = 3
Output: [101,111,121,131,141,999]
Explanation:
The first few palindromes of length 3 are:
101, 111, 121, 131, 141, 151, 161, 171, 181, 191, 202, ...
The 90th palindrome of length 3 is 999.

Example 2:

Input: queries = [2,4,6], intLength = 4
Output: [1111,1331,1551]
Explanation:
The first six palindromes of length 4 are:
1001, 1111, 1221, 1331, 1441, and 1551.

 

Constraints:

  • 1 <= queries.length <= 5 * 104
  • 1 <= queries[i] <= 109
  • 1 <= intLength <= 15

Approach Overview

Problem Overview: Given several queries and a target digit length intLength, return the k-th smallest palindrome of that length for each query. If the k-th palindrome does not exist, return -1. The key observation: a palindrome is completely defined by its first half.

Approach 1: Two-parts Mirror Approach (O(q) time, O(1) space)

Instead of generating every palindrome, compute it directly. For a palindrome with length L, only the first ceil(L/2) digits are independent. Treat this half as a number range starting from 10^(halfLen-1). For a query k, the prefix becomes start + k - 1. Mirror this prefix to construct the full palindrome: append the reverse of the prefix, skipping the last digit when the length is odd. If the prefix exceeds the allowed range, the requested palindrome does not exist. This approach avoids iteration and uses simple math and array processing.

Approach 2: Iterative Digit Construction (O(q * L) time, O(1) space)

Another way is to build each palindrome digit by digit. Determine the prefix number corresponding to the query, then construct the palindrome by iterating over the digits and placing mirrored digits at both ends. For odd-length palindromes, the middle digit is written once. This method performs explicit digit operations rather than string reversal or arithmetic mirroring. It is slightly more verbose but works well in low-level languages like C where manual digit handling is common.

Recommended for interviews: The Two-parts Mirror approach is what interviewers expect. Recognizing that only half the digits determine a palindrome reduces the problem to simple arithmetic indexing. The iterative construction method still shows understanding of palindrome structure, but the mirror math approach demonstrates stronger algorithmic insight and achieves optimal O(q) time.

Approach 1: Two-parts Mirror Approach

One way to solve the problem is by utilizing the properties of palindromes. For any given length of palindrome — whether it is odd or even, it can be generated by mirroring the relevant portion of the number. Using a step-counter, iterate through possible leading halves and mirror these to generate palindromes. This approach takes advantage of simple arithmetic to generate palindromes.

This Python function defines a helper function kthPalindrome to compute the k-th smallest palindrome with given length. It calculates the necessary half length, checks if k is beyond the possible range, constructs the half palindrome, and then mirrors it appropriately.

Code

PythonJavaScriptJava

Python

JavaScript

Java

Complexity

Time Complexity: O(n), where n is the length of queries. For each query, the operation is constant time.
Space Complexity: O(1), since computations do not require extra space related to the size of the input.

Try this approach in the editor →

Approach 2: Iterative Digit Construction

In this approach, instead of calculating using a mirrored half, iterate over possible values and construct palindromes digit by digit. For each digit length possibility, cross verify each candidate to identify queries[i] number of palindromes. This is more direct but potentially less efficient due to the complete construction attempts.

This C code anatomizes the process of constructing numeric arrays and copying to create palindrome integers.
The iterative construction may be less optimal when compared to direct computations.

Code

C

C

Complexity

Time Complexity: O(n) for queries.
Space Complexity: O(1).

Try this approach in the editor →

Approach 3: Default Approach

Code

PythonJavaC++GoTypeScriptRust

Python

Java

C++

Go

TypeScript

Rust

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Two-parts Mirror Approach

Time Complexity: O(n), where n is the length of queries. For each query, the operation is constant time.
Space Complexity: O(1), since computations do not require extra space related to the size of the input.

Iterative Digit Construction

Time Complexity: O(n) for queries.
Space Complexity: O(1).

Default Approach—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Two-parts Mirror ApproachO(q)O(1)Best general solution. Directly computes the k-th palindrome using prefix math.
Iterative Digit ConstructionO(q * L)O(1)Useful in low-level implementations where digits are constructed manually.

Video Solution

Find Palindrome With Fixed Length | Leetcode 2217 | Pattern Maths | Contest 286 🔥🔥 • Coding Decoded • 1,995 views views

Watch 8 more video solutions →

Frequently Asked Questions

Is Find Palindrome With Fixed Length easy or hard?
This problem is classified as Medium. The implementation is straightforward once you realize that only half of the digits determine the palindrome, but identifying that mathematical shortcut is the main challenge.
Find Palindrome With Fixed Length Python/Java solution
Python and Java solutions typically implement the mirror approach: compute the prefix, convert it to a string, reverse the required portion, and append it to form the palindrome. JavaScript follows the same idea, while C implementations often construct digits manually.
How to solve Find Palindrome With Fixed Length in O(q)?
Compute the length of the independent prefix as ceil(intLength / 2). The smallest prefix is 10^(prefixLen-1). For query k, calculate prefix = start + k - 1. If the prefix exceeds the maximum allowed prefix, return -1. Otherwise mirror the prefix to form the full palindrome.
What is the best approach for Find Palindrome With Fixed Length?
The best approach is the Two-parts Mirror method. Only the first half of a palindrome determines the entire number, so you compute the prefix for each query and mirror it to form the full palindrome. This avoids generating all palindromes and runs in O(q) time with O(1) extra space.
Is Find Palindrome With Fixed Length asked at Google/Amazon/Meta?
Palindrome construction and numeric indexing problems appear frequently in interviews at companies like Google, Amazon, and Meta. Variants that require generating or counting palindromes are common because they test mathematical reasoning and string manipulation.
What data structure is used in Find Palindrome With Fixed Length?
The problem mainly relies on arrays to store queries and results, along with mathematical operations to construct palindromes. No complex data structures are required since the palindrome is derived directly from numeric prefixes.
What is the time complexity of Find Palindrome With Fixed Length?
The optimal solution runs in O(q) time where q is the number of queries. Each query performs constant-time arithmetic to compute the prefix and mirror it into a palindrome. Space complexity remains O(1) apart from the output array.

Ready to solve this problem?

Practice Find Palindrome With Fixed Length with our built-in code editor and test cases.

Practice on FleetCode
Previous

Find the Closest Palindrome

Next

Lexicographically Smallest Beautiful String