What is the time complexity of Find the Closest Palindrome?

The optimal solution has a time complexity of O(log n).

What data structures are used to solve Find the Closest Palindrome?

This problem uses Math, String. Understanding these concepts is essential for solving this Hard problem efficiently.

What are the key insights for solving Find the Closest Palindrome?

Insight 1: Palindromes are symmetric, so the first half determines the second half. We can generate candidate palindromes by manipulating the first half of the input number. Insight 2: Consider edge cases like numbers close to powers of 10 (e.g., 100, 99) and extremely large numbers to ensure the generated palindromes are within a reasonable range and valid.

Which companies ask LeetCode 564. Find the Closest Palindrome in interviews?

This problem is frequently asked at Yelp.

JavaScript is required for the full interactive experience. However, all content is accessible without JavaScript.

Find the Closest Palindrome - LeetCode 564 Solution

Q: How to solve Find the Closest Palindrome?

The solution generates a set of candidate palindromes based on the input number. These candidates include palindromes formed by decrementing, keeping, and incrementing the first half of the input number. It also includes palindromes that are one less than the smallest number with the same number of digits, and one more than the largest number with the same number of digits, handling edge cases around powers of 10. The code then iterates through the candidates, computes the absolute difference between each candidate and the input number, and selects the candidate with the smallest difference. If there's a tie in the difference, it selects the smaller palindrome. The result is returned as a string.

Find the Closest Palindrome - Complete Solution Guide

Find the Closest Palindrome is LeetCode problem 564, a Hard level challenge. This complete guide provides step-by-step explanations, multiple solution approaches, and optimized code in python3, java, cpp, c.

Problem Statement

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

Detailed Explanation

The problem requires finding the closest palindromic integer to a given integer (represented as a string). The closest integer shouldn't be the number itself, and if there's a tie (equal absolute differences), the smaller palindrome should be returned. The input 'n' is a string representing an integer between 1 and 10^18 - 1, with no leading zeros.

Solution Approach

The solution generates a set of candidate palindromes based on the input number. These candidates include palindromes formed by decrementing, keeping, and incrementing the first half of the input number. It also includes palindromes that are one less than the smallest number with the same number of digits, and one more than the largest number with the same number of digits, handling edge cases around powers of 10. The code then iterates through the candidates, computes the absolute difference between each candidate and the input number, and selects the candidate with the smallest difference. If there's a tie in the difference, it selects the smaller palindrome. The result is returned as a string.

Step-by-Step Algorithm

Step 1: Determine the length of the input string 'n'.
Step 2: Convert the input string 'n' to an integer (or long).
Step 3: Create a set (or array in C) of candidate palindromes. Add two initial candidates: 10^(length - 1) - 1 and 10^length + 1. These cover the cases where the closest palindrome has fewer or more digits.
Step 4: Extract the prefix of 'n', which is the first (length + 1) // 2 digits.
Step 5: Generate palindromes by modifying the prefix. Iterate through prefix - 1, prefix, and prefix + 1. For each modified prefix, create a palindrome by mirroring it. If length is odd, exclude the last digit of the mirrored part.
Step 6: Convert generated palindromes from Step 5 into integers (or longs) and add them to the set of candidates.
Step 7: Remove the original number 'n' from the set of candidates to ensure we're returning a different palindrome.
Step 8: Iterate through the candidates, calculate the absolute difference between each candidate and 'n'.
Step 9: Keep track of the minimum difference found so far and the corresponding candidate.
Step 10: If a candidate has a smaller difference, update the minimum difference and the result. If the difference is equal to the minimum difference, update the result with the smaller candidate.
Step 11: Convert the final result back to a string and return it.

Key Insights

Insight 1: Palindromes are symmetric, so the first half determines the second half. We can generate candidate palindromes by manipulating the first half of the input number.
Insight 2: Consider edge cases like numbers close to powers of 10 (e.g., 100, 99) and extremely large numbers to ensure the generated palindromes are within a reasonable range and valid.
Insight 3: Need to efficiently compare distances and handle ties, favoring the smaller palindrome in case of equal distance.

Complexity Analysis

Time Complexity: O(log n)

Space Complexity: O(1)

Topics

This problem involves: Math, String.

Companies

Asked at: Yelp.

Find the Closest Palindrome | LeetCode 564

Hard

Math String

Time: O(log n)Space: O(1)

Solution Code

Available in:

import java.util.HashSet;
import java.util.Set;

class Solution {
    public String nearestPalindromic(String n) {
        int l = n.length();
        long n_int = Long.parseLong(n);
        
        Set<Long> candidates = new HashSet<>();

        candidates.add((long)Math.pow(10, l - 1) - 1);
        candidates.add((long)Math.pow(10, l) + 1);

        long prefix_val = Long.parseLong(n.substring(0, (l + 1) / 2));
        for (long p_val : new long[]{prefix_val - 1, prefix_val, prefix_val + 1}) {
            String p_str = String.valueOf(p_val);
            String cand_str;
            if (l % 2 == 1) {
                cand_str = p_str + new StringBuilder(p_str.substring(0, p_str.length() - 1)).reverse().toString();
            } else {
                cand_str = p_str + new StringBuilder(p_str).reverse().toString();
            }
            candidates.add(Long.parseLong(cand_str));
        }
            
        candidates.remove(n_int);
        
        long min_diff = Long.MAX_VALUE;
        long result = -1;
        
        for (long cand : candidates) {
            long diff = Math.abs(cand - n_int);
            if (diff < min_diff) {
                min_diff = diff;
                result = cand;
            } else if (diff == min_diff) {
                result = Math.min(result, cand);
            }
        }
                
        return String.valueOf(result);
    }
}

View Full Solution on GitHubGitHub Solution View on LeetCodeLeetCode

Problem Info

Description

Problem 564: Find the Closest Palindrome - Detailed explanation and solution approaches.

Topics

Math String

Companies

Yelp

Stats

Difficulty:Hard

Languages:4

Companies:1

Problem #:564

Problem Explanation

💡

Think Before You Code

🤔 Ask Yourself

→What is the input? What output do I need?
→Can I solve a smaller version of this problem first?
→What patterns have I seen in similar problems?

✏️ Try This First

Before looking at the solution, try to solve it on paper with a simple example!

🚀 Try on LeetCode

Solution Approach

📋

Step-by-Step Solution

11 steps

1
Step 1: Determine the length of the input string 'n'.
2
Step 2: Convert the input string 'n' to an integer (or long).
3
Step 3: Create a set (or array in C) of candidate palindromes. Add two initial candidates: 10^(length - 1) - 1 and 10^length + 1. These cover the cases where the closest palindrome has fewer or more digits.
4
Step 4: Extract the prefix of 'n', which is the first (length + 1) // 2 digits.
5
Step 5: Generate palindromes by modifying the prefix. Iterate through prefix - 1, prefix, and prefix + 1. For each modified prefix, create a palindrome by mirroring it. If length is odd, exclude the last digit of the mirrored part.
6
Step 6: Convert generated palindromes from Step 5 into integers (or longs) and add them to the set of candidates.
7
Step 7: Remove the original number 'n' from the set of candidates to ensure we're returning a different palindrome.
8
Step 8: Iterate through the candidates, calculate the absolute difference between each candidate and 'n'.
9
Step 9: Keep track of the minimum difference found so far and the corresponding candidate.
10
Step 10: If a candidate has a smaller difference, update the minimum difference and the result. If the difference is equal to the minimum difference, update the result with the smaller candidate.
11
Step 11: Convert the final result back to a string and return it.

💡

Pro Tip for Students

Try tracing through each step with a small example on paper before coding. Understanding "why" each step happens is more important than memorizing the code!

⚡

Complexity Analysis

⏱️

Time Complexity

O(log n)

🚀 Logarithmic - Very efficient! Halves the problem each step.

💾

Space Complexity

O(1)

💪 Constant space - Uses same memory regardless of input!

📝

Why?

The time complexity is O(log n) because the number of candidate palindromes generated is constant (independent of the size of n). Finding the minimum difference iterates through a constant number of candidates. Converting to String takes O(number of digits) which is log n. The space complexity is O(1) since the size of the candidate set remains constant regardless of the input number 'n'. We use a constant number of variables.

📖New to Big O? Click to learn more

Big O Notation - Quick Guide

O(1)Best - Instant

O(log n)Excellent - Binary Search

O(n)Good - One loop

O(n log n)OK - Sorting

O(n²)Slow - Nested loops

O(2ⁿ)Very Slow - Recursion

Alternative Approaches

Brute Force

Iterate through integers near 'n' and check if they are palindromes. Stop when you find the closest palindrome.

Time: O(n)Space: O(1)

Trade-offs: This is inefficient as it may require checking a large number of integers. The main solution is much faster due to constant time generation of candidate palindromes. Brute force would be highly inefficient for large inputs.

✨

Key Insights

1Insight 1: Palindromes are symmetric, so the first half determines the second half. We can generate candidate palindromes by manipulating the first half of the input number.
2Insight 2: Consider edge cases like numbers close to powers of 10 (e.g., 100, 99) and extremely large numbers to ensure the generated palindromes are within a reasonable range and valid.
3Insight 3: Need to efficiently compare distances and handle ties, favoring the smaller palindrome in case of equal distance.

📚

Key Terms Explained

For Students

String

A sequence of characters. Like a word or sentence in programming!

Edge Cases

Edge case 1: Input '1'. The code correctly returns '0' because it considers the power of 10 boundaries.
Edge case 2: Input '10'. The candidate set will include 9 (10^(2-1) - 1) and 11 (palindrome created by prefix 1 which results to '11'). The code will return 9 since abs(9-10) < abs(11-10).
Edge case 3: Input '99'. The code handles it by generating palindromes 98, 99, 100. The power of 10 cases are also considered (e.g., 101). The algorithm will choose 101.
Edge case 4: Large numbers near 10^18-1. The use of `long` in Java/C++ and `int` in Python (for intermediate values) allows the code to correctly handle numbers of up to 10^18-1.
Edge case 5: Palindromes themselves. The algorithm correctly excludes n from the candidate list ensuring a different palindrome is returned.

⚠️

Common Mistakes to Avoid

✗Common mistake 1: Not handling the edge cases related to powers of 10 correctly (e.g., numbers like 100, 1000).

✗Common mistake 2: Not considering the case where the closest palindrome might have a different number of digits than the input number.

✗Common mistake 3: Incorrectly handling ties, where the smaller palindrome is not selected when the absolute differences are equal.

✗Common mistake 4: Integer overflow when calculating candidate palindromes, especially with large input numbers. Using long data type prevents the overflow.

✗Common mistake 5: Forgetting to exclude the input number itself from the set of candidate palindromes.

✅

Learning Tip

Every mistake is a learning opportunity! When you make an error, understand why it happened before moving on.

🌍

Where is This Used in Real Life?

💼Real-world scenario 1: Data validation. Ensuring user input is close to a desired palindromic value.

🏦Real-world scenario 2: Number pattern generation. Generating near-palindromic numbers for artistic or mathematical purposes.

🎮Real-world scenario 3: Error correction. Identifying the closest valid palindromic code given a potentially corrupted input code.

💡Understanding real-world applications helps you see the "why" behind algorithms. It's not just about passing interviews—these concepts power the apps and websites you use every day!

Author's Notes

💡 Key Insight

When dealing with arrays, always consider if sorting would simplify the problem. Many array problems have O(n) solutions using hash maps or two-pointer technique.

🎯 Interview Tip

Hard problems often combine multiple techniques. Break the problem into sub-problems.

⚠️ Watch Out

Always test your solution with edge cases: empty input, single element, and boundary values.

Written by Saswata Mondal

Software Engineer • Algorithms Enthusiast • Interview Coach

👨‍💻

About the Author

👨‍💻

Saswata MondalAuthor400+ LC Problems

B.Tech CSE, IEM Kolkata | LeetCode Rating: 1672 (Top 15%)

Certified: IBM Java Developer, NPTEL Programming in Java

Last updated: June 25, 2024LeetCode Profile GitHub

This solution has been crafted based on my experience solving 400+ LeetCode problems. Each explanation is designed to help you understand the underlying concepts, not just memorize the code.

Community Tips & Insights

In a real interview, always clarify constraints first. Ask about input size and value ranges.

@TechLeadJul 13

Don't forget to handle the edge case when the input is empty. Many candidates miss this in interviews.

@DevExpert92Jul 6

❓

Frequently Asked Questions

How do I handle string manipulation efficiently?

In languages with immutable strings (Java, Python, C#), use StringBuilder/list to avoid O(n) concatenation cost. Consider using character arrays for in-place modifications. For pattern matching, consider KMP or Rabin-Karp for O(n+m) complexity.

How do I approach hard algorithm problems?

Hard problems often require: 1) Breaking down into subproblems, 2) Combining multiple advanced techniques, 3) Careful optimization of brute force. Start with a working solution (even O(n²) or worse), then optimize. Draw examples, identify patterns, and think about what makes this problem unique.

How should I practice algorithm problems effectively?

Focus on understanding patterns rather than memorizing solutions. After solving a problem, review optimal solutions and understand the intuition. Group similar problems to recognize patterns. Practice explaining your approach out loud. Review problems after a few days to test retention.

What is the optimal approach for "Find the Closest Palindrome"?

For this hard-level Math problem, the key is to identify the core pattern. Analyze the input constraints to determine acceptable time complexity. Consider whether string techniques can optimize the solution. Always handle edge cases and validate your approach with examples before coding.

🤖 Need help with this problem?