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 * 1041 <= queries[i] <= 1091 <= intLength <= 15Problem 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.
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.
Python
JavaScript
Java
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.
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.
C
Time Complexity: O(n) for queries.
Space Complexity: O(1).
| Approach | Complexity |
|---|---|
| Two-parts Mirror Approach | Time Complexity: O(n), where n is the length of queries. For each query, the operation is constant time. |
| Iterative Digit Construction | Time Complexity: O(n) for queries. |
| Default Approach | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Two-parts Mirror Approach | O(q) | O(1) | Best general solution. Directly computes the k-th palindrome using prefix math. |
| Iterative Digit Construction | O(q * L) | O(1) | Useful in low-level implementations where digits are constructed manually. |
Find Palindrome With Fixed Length | Leetcode 2217 | Pattern Maths | Contest 286 🔥🔥 • Coding Decoded • 1,961 views views
Watch 8 more video solutions →Practice Find Palindrome With Fixed Length with our built-in code editor and test cases.
Practice on FleetCode