LeetCode 2217 - Find Palindrome With Fixed Length

The problem asks us to find the k-th smallest positive palindrome of a fixed length for multiple queries. Specifically, we are given an array queries where each element indicates the position of a palindrome we need to find, and an integer intLength which specifies the number…

leetcodemediumarraymath

LeetCode Problem 2217

Difficulty: 🟡 Medium
Topics: Array, Math

Solution

Problem Understanding

The problem asks us to find the k-th smallest positive palindrome of a fixed length for multiple queries. Specifically, we are given an array queries where each element indicates the position of a palindrome we need to find, and an integer intLength which specifies the number of digits in the palindromes we are interested in. A palindrome is a number that reads the same forwards and backwards, and leading zeros are not allowed. For each query, if the k-th palindrome does not exist (because k is too large), we should return -1.

The input queries can have up to 50,000 elements, and each query value can be as large as 10^9. The integer length can be up to 15. This means a brute-force approach that generates all palindromes up to 10^15 is infeasible. The constraints tell us we need an algorithm that can compute the k-th palindrome directly without enumerating all smaller ones.

Edge cases include small lengths (like intLength = 1) and very large queries where the requested palindrome does not exist. Palindromes cannot start with zero, so for length greater than 1, the first digit must be at least 1. Queries exceeding the total number of palindromes of a given length must return -1.

Approaches

The brute-force approach would involve generating all palindromes of the given length sequentially and then picking the k-th palindrome for each query. While conceptually simple, it is extremely inefficient because the number of palindromes grows exponentially with length, especially for intLength > 10. This approach would be too slow and consume too much memory for large inputs.

The optimal approach relies on the key observation that a palindrome is completely determined by its first half (or first half plus middle digit if the length is odd). For example, for a 5-digit palindrome abcde, the number must satisfy a=e, b=d, and c can be any digit. Therefore, if we enumerate all possible first halves, we can construct the corresponding full palindrome directly. Using this, we can compute the k-th palindrome without generating all previous ones. The first half must not start with zero. We can compute the k-th first half as an integer offset from the minimum possible first half for the given length, and then mirror it to generate the palindrome.

Approach Time Complexity Space Complexity Notes
Brute Force O(10^(intLength/2) * len(queries)) O(10^(intLength/2)) Generate all palindromes sequentially and index them. Too slow for large lengths.
Optimal O(len(queries) * intLength) O(len(queries)) Compute first half directly, mirror it, and handle odd/even length.

Algorithm Walkthrough

  1. Compute the number of digits in the first half of the palindrome. If the length is intLength, let halfLength = (intLength + 1) // 2.
  2. Compute the smallest possible first half as start = 10^(halfLength - 1). This ensures no leading zeros.
  3. For each query k in queries:

a. Compute the first half of the k-th palindrome as firstHalf = start + k - 1.

b. Check if the number of digits in firstHalf exceeds halfLength. If it does, it means the k-th palindrome does not exist, so append -1 to the answer.

c. Otherwise, convert firstHalf to a string. Mirror it to form the full palindrome. If intLength is odd, exclude the last digit of the first half when mirroring.

d. Convert the mirrored string back to an integer and append it to the result. 4. Return the array of results.

Why it works: By calculating the first half directly and mirroring it, we guarantee the number is a palindrome of the correct length. The arithmetic ensures that queries exceeding the total number of possible palindromes are correctly handled by returning -1.

Python Solution

from typing import List

class Solution:
    def kthPalindrome(self, queries: List[int], intLength: int) -> List[int]:
        halfLength = (intLength + 1) // 2
        start = 10 ** (halfLength - 1)
        result = []
        
        for k in queries:
            firstHalf = start + k - 1
            if len(str(firstHalf)) > halfLength:
                result.append(-1)
                continue
            
            firstHalfStr = str(firstHalf)
            if intLength % 2 == 0:
                fullPalindrome = firstHalfStr + firstHalfStr[::-1]
            else:
                fullPalindrome = firstHalfStr + firstHalfStr[:-1][::-1]
            
            result.append(int(fullPalindrome))
        
        return result

In the implementation, we first calculate halfLength and start to define the range of valid first halves. For each query, we increment the starting half by k - 1 to reach the k-th first half. We check whether this first half exceeds the allowed number of digits to handle invalid queries. Then we construct the full palindrome using string manipulation, mirroring the first half appropriately for odd or even lengths. The result is collected in a list and returned.

Go Solution

import (
    "strconv"
)

func kthPalindrome(queries []int, intLength int) []int64 {
    halfLength := (intLength + 1) / 2
    start := int64(1)
    for i := 1; i < halfLength; i++ {
        start *= 10
    }
    
    result := make([]int64, len(queries))
    
    for i, k := range queries {
        firstHalf := start + int64(k-1)
        if len(strconv.FormatInt(firstHalf, 10)) > halfLength {
            result[i] = -1
            continue
        }
        
        firstHalfStr := strconv.FormatInt(firstHalf, 10)
        var fullPalindromeStr string
        if intLength%2 == 0 {
            rev := reverseString(firstHalfStr)
            fullPalindromeStr = firstHalfStr + rev
        } else {
            rev := reverseString(firstHalfStr[:len(firstHalfStr)-1])
            fullPalindromeStr = firstHalfStr + rev
        }
        
        palindrome, _ := strconv.ParseInt(fullPalindromeStr, 10, 64)
        result[i] = palindrome
    }
    
    return result
}

func reverseString(s string) string {
    runes := []rune(s)
    for i, j := 0, len(runes)-1; i < j; i, j = i+1, j-1 {
        runes[i], runes[j] = runes[j], runes[i]
    }
    return string(runes)
}

In Go, we use strconv for string conversion and implement a helper function reverseString to mirror the first half. The arithmetic and logic mirror the Python version, and care is taken to handle int64 conversion and overflow.

Worked Examples

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

Query firstHalf Palindrome
1 10 101
2 11 111
3 12 121
4 13 131
5 14 141
90 99 999

Example 2: queries = [2,4,6], intLength = 4

Query firstHalf Palindrome
2 11 1111
4 13 1331
6 15 1551

Complexity Analysis

Measure Complexity Explanation
Time O(len(queries) * intLength) Each query requires constructing a string of length roughly intLength for the palindrome.
Space O(len(queries)) Storing the result array of length equal to the number of queries.

The optimal algorithm scales linearly with the number of queries and the length of each palindrome, which is efficient given the constraints. No extra memory is used beyond the result array.

Test Cases

# Provided examples
assert Solution().kthPalindrome([1,2,3,4,5,90], 3) == [101,111,121,131,141,999]
assert Solution().kthPalindrome([2,4,6], 4) == [1111,1331,1551]

# Boundary tests
assert Solution().kthPalindrome([1], 1) == [1]           # smallest 1-digit palindrome
assert Solution().kthPalindrome([10], 1) == [10]         # invalid, should return -1
assert Solution().kthPalindrome([1,2,9], 2) == [11,22,99] # two-digit palindromes
assert Solution().kthPalindrome([100], 3) == [-1]         # query exceeds total palindromes
assert Solution().kthPalindrome([1, 1000], 5) == [10001, -1] # mixed valid/invalid