{x}
blog image

Find Palindrome With Fixed Length

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

Solution Explanation

This problem asks us to find the k-th smallest palindrome of a given length. The solution leverages the observation that palindromes are symmetric. We only need to generate the first half (or first half plus one if the length is odd) of the palindrome, and then mirror it to create the full palindrome.

Approach:

  1. Calculate the Length of the First Half: The code first determines the length of the first half (l) of the palindrome. If intLength is odd, l will be (intLength + 1) // 2; otherwise, it's intLength // 2.

  2. Determine the Range: It then calculates the starting and ending numbers for the first half. The starting number is 10(l-1) (the smallest number with l digits), and the ending number is 10l - 1 (the largest number with l digits).

  3. Iterate through Queries: The code iterates through each query q in the queries array.

  4. Calculate the First Half: For each query, it calculates the corresponding number v in the first half of the palindrome using the formula v = start + q - 1. This directly maps the query index to the numerical value of the first half.

  5. Handle Out-of-Bounds Cases: If v exceeds the end value, it means there's no such palindrome, so it adds -1 to the ans array.

  6. Construct the Palindrome: If v is within the bounds, it converts v to a string s. Then, it reverses the string (s[::-1] in Python, new StringBuilder(s).reverse() in Java, etc.) and concatenates a portion of the reversed string to the original string s to create a palindrome. The amount concatenated depends on whether intLength is odd or even.

  7. Convert back to Integer: Finally, the resulting palindrome string s is converted back to an integer and added to the ans array.

  8. Return the Result: The function returns the ans array containing the k-th palindromes or -1 if no such palindrome exists.

Time Complexity Analysis:

The dominant operation is iterating through the queries. The operations within the loop (string manipulations, conversions) take constant time relative to the input size. Therefore, the overall time complexity is O(N), where N is the length of the queries array.

Space Complexity Analysis:

The space complexity is O(N) as well because we are storing the results in the ans array. The space used for string manipulations is relatively small and constant compared to N.

Example Walkthrough (Python):

Let's consider queries = [1, 2, 3], intLength = 3.

  1. l becomes (3 + 1) // 2 = 2.
  2. start is 10(2-1) = 10, end is 102 - 1 = 99.
  3. For q = 1, v is 10 + 1 - 1 = 10. s becomes "10", and after mirroring, it becomes "101".
  4. For q = 2, v is 10 + 2 - 1 = 11. s becomes "11", and after mirroring, it becomes "111".
  5. For q = 3, v is 10 + 3 - 1 = 12. s becomes "12", and after mirroring, it becomes "121".
  6. The function returns [101, 111, 121].

The provided code in different languages implements this approach effectively. The core logic remains the same across all implementations, only the syntax varies.