Is Find Palindrome With Fixed Length easy or hard?

This problem is classified as Medium. The implementation is straightforward once you realize that only half of the digits determine the palindrome, but identifying that mathematical shortcut is the main challenge.

Find Palindrome With Fixed Length Python/Java solution

Python and Java solutions typically implement the mirror approach: compute the prefix, convert it to a string, reverse the required portion, and append it to form the palindrome. JavaScript follows the same idea, while C implementations often construct digits manually.

How to solve Find Palindrome With Fixed Length in O(q)?

Compute the length of the independent prefix as ceil(intLength / 2). The smallest prefix is 10^(prefixLen-1). For query k, calculate prefix = start + k - 1. If the prefix exceeds the maximum allowed prefix, return -1. Otherwise mirror the prefix to form the full palindrome.

What is the best approach for Find Palindrome With Fixed Length?

The best approach is the Two-parts Mirror method. Only the first half of a palindrome determines the entire number, so you compute the prefix for each query and mirror it to form the full palindrome. This avoids generating all palindromes and runs in O(q) time with O(1) extra space.

Is Find Palindrome With Fixed Length asked at Google/Amazon/Meta?

Palindrome construction and numeric indexing problems appear frequently in interviews at companies like Google, Amazon, and Meta. Variants that require generating or counting palindromes are common because they test mathematical reasoning and string manipulation.

What data structure is used in Find Palindrome With Fixed Length?

The problem mainly relies on arrays to store queries and results, along with mathematical operations to construct palindromes. No complex data structures are required since the palindrome is derived directly from numeric prefixes.

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

The optimal solution runs in O(q) time where q is the number of queries. Each query performs constant-time arithmetic to compute the prefix and mirror it into a palindrome. Space complexity remains O(1) apart from the output array.

Description Hints 2 Solution Video 10:35

2217. Find Palindrome With Fixed Length

Medium38.0% acceptance1 company

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 90^th 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 * 10⁴
1 <= queries[i] <= 10⁹
1 <= intLength <= 15

Asked at 1 company

VMware

Topics

Array Math

Hints open one at a time

Hint 1

For any value of queries[i] and intLength, how can you check if there exists at least queries[i] palindromes of length intLength?

Hint 2

Since a palindrome reads the same forwards and backwards, consider how you can efficiently find the first half (ceil(intLength/2) digits) of the palindrome.

10:35

Still stuck?Read 3 approaches, or watch a walkthrough.

Open solution