#2217

Medium

LeetCode Problem Workspace

Find Palindrome With Fixed Length

Find the smallest palindromes of a given length for specific queries with mathematical and array manipulation.

Problem Statement

Given an integer array queries and a positive integer intLength, return an array answer such that answer[i] is the queries[i]-th smallest palindrome of length intLength. If no such palindrome exists, return -1 for that index. A palindrome is a number that reads the same backwards and forwards and cannot have leading zeros.

For example, if queries = [1,2,3,4,5,90] and intLength = 3, the palindromes are: 101, 111, 121, 131, 141, 999. You should determine the palindromes corresponding to each query and handle cases where a query is too large.

Examples

Example 1

Input: queries = [1,2,3,4,5,90], intLength = 3

Output: [101,111,121,131,141,999]

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]

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

Solution Approach

Identify Palindromes

The first step is to generate palindromes of the specified length. A palindrome of length intLength can be constructed by ensuring that the number reads the same forward and backward. For odd-length palindromes, you can generate the first half and mirror it, while for even-length palindromes, you mirror the entire number.

Efficient Calculation of the nth Palindrome

Instead of generating all palindromes up to queries[i], find an efficient way to compute the nth palindrome. This can be done by calculating the range of numbers that can form palindromes of the given length and then deriving the specific palindrome for each query.

Edge Case Handling

Ensure that you handle queries for palindromes that don’t exist. For instance, if the query asks for the 1000th palindrome of length 3, but the highest possible palindrome is 999, return -1 for that query.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time complexity is primarily determined by how efficiently you can calculate the nth palindrome for each query. If the approach directly constructs the palindromes in constant time, the overall time complexity would be proportional to the length of the queries array. Space complexity depends on how you store and calculate these palindromes.

What Interviewers Usually Probe

The candidate understands how to efficiently generate palindromes based on the length and query.
The candidate handles edge cases such as queries larger than the number of available palindromes.
The candidate can effectively use array and mathematical techniques to minimize computation.

Common Pitfalls or Variants

Common pitfalls

Misunderstanding how to generate palindromes efficiently, leading to excessive computation or storage.
Failing to handle edge cases where the query exceeds the number of possible palindromes.
Incorrectly assuming palindromes can have leading zeros, which is not allowed in this problem.

Follow-up variants

What if the intLength were increased, making the palindromes larger?
How would you handle queries with very large values (e.g., queries[i] near 10^9)?
What if the problem allowed leading zeros in the palindromes?

FAQ

What is the main pattern behind the 'Find Palindrome With Fixed Length' problem?

The main pattern involves generating palindromes using mathematical manipulation of numbers and efficiently handling queries for specific palindromes based on their index.

How can I efficiently generate palindromes of a fixed length?

You can generate palindromes by constructing the first half of the number and reflecting it to form the entire palindrome. The approach differs slightly for odd and even lengths.

How do I handle large queries that ask for a non-existent palindrome?

If a query asks for a palindrome that exceeds the maximum possible palindrome for a given length, return -1 for that query.

What is the time complexity of solving the 'Find Palindrome With Fixed Length' problem?

The time complexity depends on how you calculate each palindrome. Efficient generation of palindromes can keep the complexity linear in terms of the number of queries.

Can this problem be solved without generating all the palindromes upfront?

Yes, by calculating each palindrome as needed, without pre-generating the entire set, you can optimize both time and space complexity.

terminal

Solution

Solution 1

#### Python3

1

2

3

4

5

6

7

8

9

10

11

12

13

14

class Solution:
    def kthPalindrome(self, queries: List[int], intLength: int) -> List[int]:
        l = (intLength + 1) >> 1
        start, end = 10 ** (l - 1), 10**l - 1
        ans = []
        for q in queries:
            v = start + q - 1
            if v > end:
                ans.append(-1)
                continue
            s = str(v)
            s += s[::-1][intLength % 2 :]
            ans.append(int(s))
        return ans

Continue Practicing

#2221 find triangular sum of an array #2197 replace non coprime numbers in array #2195 append k integers with minimal sum