#13Ancient Vault Code II: The Palindrome Quest
Deep inside the ancient temple, the vault contains multiple chambers. In the first challenge, you only needed to check whether a code was a palindrome. Now, the challenge is harder.
Given an integer array queries and a positive integer codeLength, return an array answer where:
- answer[i] is the queries[i]th smallest positive valid vault code having exactly codeLength digits.
- Return -1 if the requested palindrome does not exist.
A valid vault code is a palindrome, meaning it reads the same from left to right and right to left. Vault codes cannot contain leading zeros.
Examples
Example 1
Input: queries = [1, 3, 5, 10]
codeLength = 3
Output: [101, 121, 141, 191]
Explanation: The first few valid 3-digit vault codes are: 101, 111, 121, 131, 141, 151, 161, 171, 181, 191, ... Therefore: 1st → 101 3rd → 121 5th → 141 10th → 191
Example 2
Input: queries = [1, 2, 4, 8]
codeLength = 4
Output: [1001, 1111, 1331, 1771]
Explanation: The first few valid 4-digit vault codes are: 1001, 1111, 1221, 1331, 1441, 1551, 1661, 1771, ...
Example 3
Input: queries = [1, 9, 90, 91]
codeLength = 2
Output: [11, 99, -1, -1]
Explanation: The positive 2-digit palindromic vault codes are: 11, 22, 33, 44, 55, 66, 77, 88, 99 Only 9 valid codes exist. Therefore, queries 90 and 91 return -1.
Constraints
- 1 <= queries.length <= 50000
- 1 <= queries[i] <= 10^9
- 1 <= codeLength <= 15
- Every value in queries represents a 1-indexed position.
- Returned vault codes must not have leading zeros.