Jobs

Interviews

Discussions

Find the Closest Palindrome

Hard

Asked by:

29 views

Topics:

StringsTwo Pointers

Given a string n representing an integer, return the closest integer (not including itself), which is a palindrome. If there is a tie, return the smaller one.

The closest is defined as the absolute difference minimized between two integers.

Example 1:

Input: n = "123"
Output: "121"

Example 2:

Input: n = "1"
Output: "0"
Explanation: 0 and 2 are the closest palindromes but we return the smallest which is 0.

Constraints:

1 <= n.length <= 18
n consists of only digits.
n does not have leading zeros.
n is representing an integer in the range [1, 10¹⁸ - 1].

Find the Closest Palindrome

Hard

Asked by:

29 views

Topics:

StringsTwo Pointers

Given a string n representing an integer, return the closest integer (not including itself), which is a palindrome. If there is a tie, return the smaller one.

The closest is defined as the absolute difference minimized between two integers.

Example 1:

Input: n = "123"
Output: "121"

Example 2:

Input: n = "1"
Output: "0"
Explanation: 0 and 2 are the closest palindromes but we return the smallest which is 0.

Constraints:

1 <= n.length <= 18
n consists of only digits.
n does not have leading zeros.
n is representing an integer in the range [1, 10¹⁸ - 1].

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 is the range of possible integer values in the input string?
If the input string is already a palindrome, should I return the original string, or the next closest palindrome?
If there are two palindromes equally close to the input, which one should I return (e.g., the smaller one lexicographically or numerically)?
Is the input string guaranteed to be a positive integer? Can it be empty or null?
What is the expected behavior if the input number is at the extreme limits, such as the maximum possible integer?

Brute Force Solution

Approach

The brute force approach to finding the closest palindrome involves checking many possibilities around the original number. It's like trying out many slight variations of the number to see if any of them are palindromes and, if so, which is closest.

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

Consider numbers smaller than the original number.
For each number smaller than the original, check if it's a palindrome. A palindrome is a number that reads the same forwards and backward.
Consider numbers larger than the original number.
For each number larger than the original, check if it's a palindrome.
Compare all the palindromes you found (both smaller and larger than the original) to the original number.
Figure out which palindrome is the closest to the original number. This is the one with the smallest difference in value from the original number.
If there are two palindromes equally close (one smaller and one larger), choose the smaller one.

Code Implementation

def find_closest_palindrome_brute_force(number):
    smaller_palindrome = None
    larger_palindrome = None
    original_number = number

    current_number = original_number - 1
    while smaller_palindrome is None and current_number >= 0:
        if str(current_number) == str(current_number)[::-1]:
            smaller_palindrome = current_number

        current_number -= 1

    current_number = original_number + 1
    while larger_palindrome is None:
        if str(current_number) == str(current_number)[::-1]:
            larger_palindrome = current_number

        current_number += 1

    # Need to handle edge cases where one palindrome doesn't exist
    if smaller_palindrome is None:
        return larger_palindrome

    if larger_palindrome is None:
        return smaller_palindrome

    smaller_difference = abs(original_number - smaller_palindrome)
    larger_difference = abs(larger_palindrome - original_number)

    # If both are equally close, choose the smaller one
    if smaller_difference <= larger_difference:
        return smaller_palindrome

    # Otherwise return the larger one
    return larger_palindrome

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(n * 10^n) – The algorithm iterates through numbers smaller and larger than the input number n. In the worst-case scenario, it might have to explore a range of numbers up to 10^n where n represents the number of digits in the input number. For each number in this range, a palindrome check, which takes O(n) time, is performed. Therefore, the overall time complexity is approximately O(n * 10^n), dominated by the potential size of the search space around n multiplied by the cost of the palindrome check.

Space Complexity

O(1) – The brute force approach described primarily involves generating and comparing numbers. While numbers smaller and larger than the original input are tested, the plain English explanation does not mention storing all generated palindromes or any other data structures that scale with the input number's magnitude (N). The only space utilized is for a few temporary variables used in calculations and comparisons, such as storing a single candidate palindrome at a time, or storing the difference between numbers. Therefore, the auxiliary space remains constant, regardless of the size of the input number N.

Optimal Solution

Approach

The trick is to find nearby palindromes instead of checking every single number. We only need to consider a few special cases based on the input number's structure to find the closest palindrome efficiently.

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

First, handle some basic cases: If the input is a single-digit number, the answer is simply one less than the number.
Consider three candidate palindromes: one made by mirroring the first half of the input number, another made by increasing the middle digit(s) of the first half before mirroring, and the last by decreasing the middle digit(s) of the first half before mirroring. Pay close attention to handling carries and borrows when incrementing or decrementing.
For example, if the number is 12345, the first half is 123. We'd mirror it to get 12321. Then we'd increment 123 to 124 and mirror it to get 12421. Finally, we decrement 123 to 122 and mirror to get 12221.
Also, consider the largest palindrome with one fewer digit (e.g., 999 if the input has four digits) and the smallest palindrome with one more digit (e.g., 1001 if the input has three digits). These are edge cases that could be the closest palindrome.
Compare the absolute differences between the input number and each of these candidate palindromes.
Return the candidate palindrome with the smallest absolute difference to the original number. If there are ties, return the smaller palindrome.

Code Implementation

def find_the_closest_palindrome(number):
    number_as_string = str(number)
    number_length = len(number_as_string)

    # Handle single-digit numbers
    if number_length == 1:
        return number - 1

    candidates = []

    # Create palindrome by mirroring the first half
    first_half = number_as_string[:(number_length + 1) // 2]
    palindrome_a = first_half + first_half[:number_length // 2][::-1]
    candidates.append(int(palindrome_a))

    # Create palindrome by incrementing first half
    first_half_incremented = str(int(first_half) + 1)

    # Need to handle carry when incrementing
    if len(first_half_incremented) > len(first_half):
        palindrome_b = str(1) + '0' * (number_length - 1) + str(1)
    else:
        palindrome_b = first_half_incremented + first_half_incremented[:number_length // 2][::-1]
    candidates.append(int(palindrome_b))

    # Create palindrome by decrementing first half
    first_half_decremented = str(int(first_half) - 1)

    # Need to handle borrow when decrementing
    if first_half_decremented == '-1':
        palindrome_c = '9' * (number_length - 1)
    else:
        palindrome_c = first_half_decremented + first_half_decremented[:number_length // 2][::-1]
    candidates.append(int(palindrome_c))

    # Add edge cases to consider
    candidates.append(10**(number_length - 1) - 1)
    candidates.append(10**number_length + 1)

    closest_palindrome = -1
    min_difference = float('inf')

    # Find the closest palindrome
    for candidate in candidates:
        difference = abs(number - candidate)

        # Tiebreaker goes to the smaller number
        if difference < min_difference:
            min_difference = difference
            closest_palindrome = candidate
        elif difference == min_difference:
            closest_palindrome = min(closest_palindrome, candidate)

    return closest_palindrome

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(n) – The dominant operations involve creating and comparing a fixed number of candidate palindromes. The length of these palindromes is at most one more or one less than the number of digits (n) in the input number. Generating each palindrome requires mirroring a portion of the input number, which takes O(n) time. Comparing the input number to each candidate palindrome also takes O(n) time. Since we're doing a fixed number of these O(n) operations, the overall time complexity is O(n).

Space Complexity

O(N) – The algorithm creates candidate palindromes based on mirroring and modifying the first half of the input number. The largest and smallest palindromes with one fewer or one more digit than the input are also created. The creation of these palindromes, which can be at most N+1 digits long, requires auxiliary space to store the digits. Therefore, the space complexity is O(N), where N is the number of digits in the input number.

Edge Cases

Case	How to Handle
Null or empty input string	Return an empty string or throw an IllegalArgumentException, depending on problem specification.
Single-character input string	Return the input string itself, as a single character is a palindrome.
Input string is already a palindrome	Return the original input string itself as it is already the closest.
Input string consists of all 9's (e.g., '999')	Incrementing this number will result in a number with one more digit (e.g., 1001), handle string manipulation to construct the appropriate palindrome.
Input string is a large number (potential for integer overflow during conversion)	Use string manipulation instead of integer conversions to avoid overflow issues.
Input string is close to the maximum integer value represented as a string.	Handle potential overflow in the increment/decrement palindrome generation steps by doing string arithmetic.
Number has leading zeros (e.g., "00121").	Ensure leading zeros are considered when finding the nearest palindrome and construct the resulting palindrome properly or trim leading zeros if appropriate for output.
Input string represents a negative number.	If negative numbers are invalid input, throw an exception; otherwise, consider the absolute value and add the negative sign back to the closest palindrome if appropriate, or specify that only positive integers should be processed.

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 is the range of possible integer values in the input string?
If the input string is already a palindrome, should I return the original string, or the next closest palindrome?
If there are two palindromes equally close to the input, which one should I return (e.g., the smaller one lexicographically or numerically)?
Is the input string guaranteed to be a positive integer? Can it be empty or null?
What is the expected behavior if the input number is at the extreme limits, such as the maximum possible integer?

Brute Force Solution

Approach

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

Consider numbers smaller than the original number.
For each number smaller than the original, check if it's a palindrome. A palindrome is a number that reads the same forwards and backward.
Consider numbers larger than the original number.
For each number larger than the original, check if it's a palindrome.
Compare all the palindromes you found (both smaller and larger than the original) to the original number.
Figure out which palindrome is the closest to the original number. This is the one with the smallest difference in value from the original number.
If there are two palindromes equally close (one smaller and one larger), choose the smaller one.

Code Implementation

def find_closest_palindrome_brute_force(number):
    smaller_palindrome = None
    larger_palindrome = None
    original_number = number

    current_number = original_number - 1
    while smaller_palindrome is None and current_number >= 0:
        if str(current_number) == str(current_number)[::-1]:
            smaller_palindrome = current_number

        current_number -= 1

    current_number = original_number + 1
    while larger_palindrome is None:
        if str(current_number) == str(current_number)[::-1]:
            larger_palindrome = current_number

        current_number += 1

    # Need to handle edge cases where one palindrome doesn't exist
    if smaller_palindrome is None:
        return larger_palindrome

    if larger_palindrome is None:
        return smaller_palindrome

    smaller_difference = abs(original_number - smaller_palindrome)
    larger_difference = abs(larger_palindrome - original_number)

    # If both are equally close, choose the smaller one
    if smaller_difference <= larger_difference:
        return smaller_palindrome

    # Otherwise return the larger one
    return larger_palindrome

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

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

First, handle some basic cases: If the input is a single-digit number, the answer is simply one less than the number.
Consider three candidate palindromes: one made by mirroring the first half of the input number, another made by increasing the middle digit(s) of the first half before mirroring, and the last by decreasing the middle digit(s) of the first half before mirroring. Pay close attention to handling carries and borrows when incrementing or decrementing.
For example, if the number is 12345, the first half is 123. We'd mirror it to get 12321. Then we'd increment 123 to 124 and mirror it to get 12421. Finally, we decrement 123 to 122 and mirror to get 12221.
Also, consider the largest palindrome with one fewer digit (e.g., 999 if the input has four digits) and the smallest palindrome with one more digit (e.g., 1001 if the input has three digits). These are edge cases that could be the closest palindrome.
Compare the absolute differences between the input number and each of these candidate palindromes.
Return the candidate palindrome with the smallest absolute difference to the original number. If there are ties, return the smaller palindrome.

Code Implementation

def find_the_closest_palindrome(number):
    number_as_string = str(number)
    number_length = len(number_as_string)

    # Handle single-digit numbers
    if number_length == 1:
        return number - 1

    candidates = []

    # Create palindrome by mirroring the first half
    first_half = number_as_string[:(number_length + 1) // 2]
    palindrome_a = first_half + first_half[:number_length // 2][::-1]
    candidates.append(int(palindrome_a))

    # Create palindrome by incrementing first half
    first_half_incremented = str(int(first_half) + 1)

    # Need to handle carry when incrementing
    if len(first_half_incremented) > len(first_half):
        palindrome_b = str(1) + '0' * (number_length - 1) + str(1)
    else:
        palindrome_b = first_half_incremented + first_half_incremented[:number_length // 2][::-1]
    candidates.append(int(palindrome_b))

    # Create palindrome by decrementing first half
    first_half_decremented = str(int(first_half) - 1)

    # Need to handle borrow when decrementing
    if first_half_decremented == '-1':
        palindrome_c = '9' * (number_length - 1)
    else:
        palindrome_c = first_half_decremented + first_half_decremented[:number_length // 2][::-1]
    candidates.append(int(palindrome_c))

    # Add edge cases to consider
    candidates.append(10**(number_length - 1) - 1)
    candidates.append(10**number_length + 1)

    closest_palindrome = -1
    min_difference = float('inf')

    # Find the closest palindrome
    for candidate in candidates:
        difference = abs(number - candidate)

        # Tiebreaker goes to the smaller number
        if difference < min_difference:
            min_difference = difference
            closest_palindrome = candidate
        elif difference == min_difference:
            closest_palindrome = min(closest_palindrome, candidate)

    return closest_palindrome

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Null or empty input string	Return an empty string or throw an IllegalArgumentException, depending on problem specification.
Single-character input string	Return the input string itself, as a single character is a palindrome.
Input string is already a palindrome	Return the original input string itself as it is already the closest.
Input string consists of all 9's (e.g., '999')	Incrementing this number will result in a number with one more digit (e.g., 1001), handle string manipulation to construct the appropriate palindrome.
Input string is a large number (potential for integer overflow during conversion)	Use string manipulation instead of integer conversions to avoid overflow issues.
Input string is close to the maximum integer value represented as a string.	Handle potential overflow in the increment/decrement palindrome generation steps by doing string arithmetic.
Number has leading zeros (e.g., "00121").	Ensure leading zeros are considered when finding the nearest palindrome and construct the resulting palindrome properly or trim leading zeros if appropriate for output.
Input string represents a negative number.	If negative numbers are invalid input, throw an exception; otherwise, consider the absolute value and add the negative sign back to the closest palindrome if appropriate, or specify that only positive integers should be processed.