Jobs

Interviews

Discussions

Find Palindrome With Fixed Length

Medium

TikTok

1 view

Topics:

ArraysStringsTwo Pointers

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

Try coding it in LeetCode

Find Palindrome With Fixed Length

Medium

TikTok

1 view

Topics:

ArraysStringsTwo Pointers

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

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the constraints on the length of the queries array and the value of palindromeLength?
What is the maximum possible value for any element within the queries array?
What should I return if palindromeLength is less than or equal to 0?
If the query-th palindrome is larger than the maximum representable integer, how should it be handled?
Are there any specific data type limitations for the queries array (e.g., 32-bit integer, 64-bit integer)?

Brute Force Solution

Approach

The brute force approach to finding a palindrome of a specific length involves generating every possible combination of characters for that length. Then, it checks if each generated string is a palindrome. This method is exhaustive, ensuring all possibilities are considered.

Here's how the algorithm would work step-by-step:

Start by creating every possible string of the required length using all available characters.
For example, if the length is 3 and you can use letters 'a' and 'b', you would create 'aaa', 'aab', 'aba', 'abb', 'baa', 'bab', 'bba', 'bbb'.
Once you have a string, check if it's a palindrome. A palindrome reads the same forwards and backward.
If the generated string is a palindrome, keep it in your results.
Continue generating and checking strings until you have considered all possible combinations.
Finally, return the list of palindromes that you found. If you need a specific one, like the smallest or largest, you can filter the list at the end.

Code Implementation

def find_palindrome_with_fixed_length_brute_force(required_length, requirement): 
    smallest_number = 10**(required_length - 1)
    largest_number = 10**required_length - 1

    for current_number in range(smallest_number, largest_number + 1): 
        number_as_string = str(current_number)
        
        # Check if the current number is a palindrome.
        if number_as_string == number_as_string[::-1]:

            # Filter palindromes based on the additional requirement.
            if current_number == requirement:
                return current_number

    # If no palindrome meets the requirements, return -1.
    return -1

Big(O) Analysis

Time Complexity

O(a^k) – The brute force approach involves generating all possible strings of length k using an alphabet of size a. This means generating a^k strings. For each of these a^k strings, we then need to check if it's a palindrome, which takes O(k) time. Therefore, the overall time complexity is O(k * a^k). However, since k (the length of the palindrome) is considered fixed, and a (the size of the alphabet) is also fixed, the palindrome check becomes a constant time operation within the scope of Big O. The dominant factor is generating the strings, making the overall time complexity O(a^k).

Space Complexity

O(L * A) – The brute force approach generates every possible string of length L, where L is the fixed length of the palindrome. If A is the number of available characters, the algorithm will potentially create and store a list of A^L strings. The memory required to store a single string is proportional to its length, L. Thus, the total auxiliary space needed is proportional to L multiplied by the number of palindromes found, which in the worst case can be all possible strings, leading to a space complexity of O(L * A^L). However, we can simplify this by noting that the question requests analysis only for the space complexity of the provided explanation, where each generated string is checked before potentially storing it. If we are only storing a constant number of palindromes (e.g., only the smallest one, or at most K palindromes) then the space complexity would be O(L) or O(K*L) respectively. But if we are potentially storing all generated strings as the explanation suggests, the space is O(L * A) if we view the character space 'A' as a constant. We are also storing a generated string of length L at a time in the auxiliary space. Since it's said we store, the space to store each generated string has to be accounted for. Therefore, the auxiliary space grows linearly with the length of the string and we consider all possible characters during generation.

Optimal Solution

Approach

The most efficient way to find a palindrome with a specific length involves constructing it directly rather than searching. We create the first half and then mirror it to form the palindrome. Adjustments are needed if we're dealing with an odd-length palindrome to handle the middle character correctly.

Here's how the algorithm would work step-by-step:

Determine the length of the palindrome we need to create.
Calculate the length of the first half of the palindrome. This is half the total length, rounding down if necessary.
Generate a number that represents the 'seed' for the palindrome. We'll use this number to build our palindrome.
Transform this number into its string representation.
Create the first half of the palindrome by taking the string representation of the number.
Make a reversed copy of this first half string.
If the palindrome length is odd, remove the last character from the reversed copy. This avoids duplicating the middle character.
Concatenate the first half and the reversed copy to form the full palindrome string.
Check if the numerical value of our 'seed' number is within the allowed range. If it's too small or too big, we can't form a valid palindrome within the given limits. Return an error if so.
Convert the resulting palindrome string back into a number.
Return this number as the answer.

Code Implementation

def find_palindrome_with_fixed_length(queries, int_length):
    results = []
    for query in queries:
        adjusted_number = query - 1
        number_as_string = str(adjusted_number)

        # Determine the length of the first half.
        first_half_length = (int_length + 1) // 2

        # If the adjusted number is too small.
        minimum_start = 10 ** (first_half_length -1)
        maximum_range = 10 ** (first_half_length)
        if adjusted_number < minimum_start -1 or adjusted_number >= maximum_range -1 :
            results.append(-1)
            continue

        first_half = number_as_string.zfill(first_half_length)
        reversed_first_half = first_half[::-1]

        # Adjust the concatenation based on even/odd length.
        if int_length % 2 == 0:
            palindrome = first_half + reversed_first_half
        else:
            palindrome = first_half + reversed_first_half[1:]

        results.append(int(palindrome))

    return results

Big(O) Analysis

Time Complexity

O(k) – The time complexity is primarily determined by the length (k) of the generated palindrome strings. Calculating the first half of the palindrome involves operations proportional to k. Reversing the first half also takes O(k) time. Concatenating the strings happens in O(k) time. Converting numbers to strings and back contributes O(k) as well, where k depends on the size of the input queries and intLength. Thus the time complexity is O(k).

Space Complexity

O(L) – The dominant space usage comes from creating string representations of the 'seed' number and its reversed copy, both having a maximum length of L, where L is the fixed length of the palindrome. Specifically, the first half of the palindrome and its reversed version are stored as strings. Therefore, the auxiliary space is proportional to the length L of the palindrome. Other variables used, like the palindrome length and seed number, occupy constant space.

Edge Cases

Case	How to Handle
Null or empty queries array	Return an empty array since there are no queries to process.
palindromeLength is zero or negative	Return an array filled with -1, indicating no such palindrome exists because length has to be positive.
palindromeLength is extremely large, causing integer overflow when calculating the range of palindromes	Use a data type like 'long' to handle large palindrome lengths and check for overflows during palindrome generation.
Queries contain very large numbers that exceed the total number of possible palindromes for the given palindromeLength	Return -1 for queries that exceed the maximum possible palindrome index.
palindromeLength is even	The solution should correctly construct palindromes with an even number of digits, mirroring the first half.
palindromeLength is odd	The solution should correctly construct palindromes with an odd number of digits, including a central digit.
queries array contains duplicate query values	Process each query independently; duplicate queries simply result in the same palindrome being computed multiple times.
The smallest possible palindrome exceeds the maximum integer value	Return -1 for all queries as no valid integer palindrome can be generated in the current environment.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the constraints on the length of the queries array and the value of palindromeLength?
What is the maximum possible value for any element within the queries array?
What should I return if palindromeLength is less than or equal to 0?
If the query-th palindrome is larger than the maximum representable integer, how should it be handled?
Are there any specific data type limitations for the queries array (e.g., 32-bit integer, 64-bit integer)?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

Start by creating every possible string of the required length using all available characters.
For example, if the length is 3 and you can use letters 'a' and 'b', you would create 'aaa', 'aab', 'aba', 'abb', 'baa', 'bab', 'bba', 'bbb'.
Once you have a string, check if it's a palindrome. A palindrome reads the same forwards and backward.
If the generated string is a palindrome, keep it in your results.
Continue generating and checking strings until you have considered all possible combinations.
Finally, return the list of palindromes that you found. If you need a specific one, like the smallest or largest, you can filter the list at the end.

Code Implementation

def find_palindrome_with_fixed_length_brute_force(required_length, requirement): 
    smallest_number = 10**(required_length - 1)
    largest_number = 10**required_length - 1

    for current_number in range(smallest_number, largest_number + 1): 
        number_as_string = str(current_number)
        
        # Check if the current number is a palindrome.
        if number_as_string == number_as_string[::-1]:

            # Filter palindromes based on the additional requirement.
            if current_number == requirement:
                return current_number

    # If no palindrome meets the requirements, return -1.
    return -1

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

Determine the length of the palindrome we need to create.
Calculate the length of the first half of the palindrome. This is half the total length, rounding down if necessary.
Generate a number that represents the 'seed' for the palindrome. We'll use this number to build our palindrome.
Transform this number into its string representation.
Create the first half of the palindrome by taking the string representation of the number.
Make a reversed copy of this first half string.
If the palindrome length is odd, remove the last character from the reversed copy. This avoids duplicating the middle character.
Concatenate the first half and the reversed copy to form the full palindrome string.
Check if the numerical value of our 'seed' number is within the allowed range. If it's too small or too big, we can't form a valid palindrome within the given limits. Return an error if so.
Convert the resulting palindrome string back into a number.
Return this number as the answer.

Code Implementation

def find_palindrome_with_fixed_length(queries, int_length):
    results = []
    for query in queries:
        adjusted_number = query - 1
        number_as_string = str(adjusted_number)

        # Determine the length of the first half.
        first_half_length = (int_length + 1) // 2

        # If the adjusted number is too small.
        minimum_start = 10 ** (first_half_length -1)
        maximum_range = 10 ** (first_half_length)
        if adjusted_number < minimum_start -1 or adjusted_number >= maximum_range -1 :
            results.append(-1)
            continue

        first_half = number_as_string.zfill(first_half_length)
        reversed_first_half = first_half[::-1]

        # Adjust the concatenation based on even/odd length.
        if int_length % 2 == 0:
            palindrome = first_half + reversed_first_half
        else:
            palindrome = first_half + reversed_first_half[1:]

        results.append(int(palindrome))

    return results

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Null or empty queries array	Return an empty array since there are no queries to process.
palindromeLength is zero or negative	Return an array filled with -1, indicating no such palindrome exists because length has to be positive.
palindromeLength is extremely large, causing integer overflow when calculating the range of palindromes	Use a data type like 'long' to handle large palindrome lengths and check for overflows during palindrome generation.
Queries contain very large numbers that exceed the total number of possible palindromes for the given palindromeLength	Return -1 for queries that exceed the maximum possible palindrome index.
palindromeLength is even	The solution should correctly construct palindromes with an even number of digits, mirroring the first half.
palindromeLength is odd	The solution should correctly construct palindromes with an odd number of digits, including a central digit.
queries array contains duplicate query values	Process each query independently; duplicate queries simply result in the same palindrome being computed multiple times.
The smallest possible palindrome exceeds the maximum integer value	Return -1 for all queries as no valid integer palindrome can be generated in the current environment.