Find Palindrome With Fixed Length
MedPrompt
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 * 1041 <= queries[i] <= 1091 <= intLength <= 15
Approaches
2 approaches with complexity analysis and trade-offs.
This naive approach involves generating and checking numbers one by one. For each query, it iterates through all numbers of the specified length, tests each for the palindrome property, and keeps a count. When the count matches the query number, the corresponding palindrome is found.
Algorithm
- For each
queryin thequeriesarray:- Initialize a counter
countto 0 and the result for this query to -1. - Determine the range of numbers to check: from
start = 10^(intLength - 1)toend = 10^intLength - 1. - Iterate through each number
numin this range. - For each
num, check if it is a palindrome. This is typically done by converting the number to a string and checking if the string is identical to its reverse. - If
numis a palindrome, incrementcount. - If
countbecomes equal to the currentqueryvalue, we have found the desired palindrome. Storenumas the result and break the inner loop. - If the loop finishes and the
query-th palindrome hasn't been found, the result remains -1. - Add the result to the final answer array.
- Initialize a counter
Walkthrough
The brute-force method directly simulates the process of finding the k-th palindrome. It starts from the smallest positive number of intLength and iterates upwards. In each step, it checks if the current number is a palindrome. A counter is maintained to track how many palindromes have been found. When this counter reaches the value specified by a query, the current number is the answer for that query. This entire process is repeated for every single query in the input array.
For example, to find the 3rd palindrome of length 3:
- Start with 100. Is it a palindrome? No.
-
- Is it a palindrome? Yes. Count = 1.
- 102...110. No.
-
- Is it a palindrome? Yes. Count = 2.
- 112...120. No.
-
- Is it a palindrome? Yes. Count = 3. This is our answer.
This is computationally expensive because the number of candidates to check can be enormous, especially for larger intLength values.
class Solution { public long[] kthPalindrome(int[] queries, int intLength) { long[] ans = new long[queries.length]; long start = (long) Math.pow(10, intLength - 1); long end = (long) Math.pow(10, intLength); // This pre-computation is slightly better but still too slow for the given constraints java.util.List<Long> palindromes = new java.util.ArrayList<>(); for (long num = start; num < end; num++) { if (isPalindrome(num)) { palindromes.add(num); } } for (int i = 0; i < queries.length; i++) { int query = queries[i]; if (query > 0 && query <= palindromes.size()) { ans[i] = palindromes.get(query - 1); } else { ans[i] = -1; } } return ans; } private boolean isPalindrome(long n) { String s = Long.toString(n); int len = s.length(); for (int i = 0; i < len / 2; i++) { if (s.charAt(i) != s.charAt(len - 1 - i)) { return false; } } return true; }}Complexity
Time
O(10^L * L + Q), where L is `intLength` and Q is the number of queries. The term `10^L * L` comes from iterating through all numbers of length L and checking if they are palindromes. This is prohibitively slow for the given constraints.
Space
O(N + P), where N is the number of queries and P is the total number of palindromes of `intLength`. In the worst case (`intLength=15`), P can be up to `9 * 10^7`, leading to high memory usage.
Trade-offs
Pros
Simple to conceptualize and implement.
Requires minimal mathematical insight.
Cons
Extremely inefficient and slow.
Will result in a 'Time Limit Exceeded' error on any reasonably large test case due to the nested loops and large search space.
Repeats the same palindrome generation work for each query.
Solutions
Solution
class Solution {public long[] kthPalindrome(int[] queries, int intLength) { int n = queries.length; long[] ans = new long[n]; int l = (intLength + 1) >> 1; long start = (long)Math.pow(10, l - 1); long end = (long)Math.pow(10, l) - 1; for (int i = 0; i < n; ++i) { long v = start + queries[i] - 1; if (v > end) { ans[i] = -1; continue; } String s = "" + v; s += new StringBuilder(s).reverse().substring(intLength % 2); ans[i] = Long.parseLong(s); } return ans; }}Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.