Watch 9 video solutions for Find Palindrome With Fixed Length, a medium level problem involving Array, Math. This walkthrough by Coding Decoded has 1,961 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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. |