Find the Closest Palindrome

Hard Arrays & Hashing Candidate Generation Original on LeetCode

Reported atUber

Find the Closest Palindrome is a hard arrays & hashing problem solved with the candidate generation pattern. The best approach, optimal (mirror the left half), runs in O(L) time and O(L) space. Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force (search outward) up.

Problem

You get a positive integer n written as a string. Return, also as a string, the palindromic integer closest to n, not counting n itself. Closeness is the absolute difference between the two numbers.

If two palindromes are equally close, return the smaller one.

Examples

Example 1

Input
n = "456"
Output
"454"
Why
454 is 2 away; the next palindromes up and down (464 and 444) are farther.

Example 2

Input
n = "99"
Output
"101"
Why
101 is 2 away while 88 is 11 away; the answer gains a digit.

Example 3

Input
n = "1"
Output
"0"
Why
0 and 2 are both 1 away; on a tie the smaller one wins.

Constraints

  • 1 <= n.length <= 18
  • n holds only digits and has no leading zeros
  • 1 <= n <= 10^18 - 1

Solve it here

Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.

00:00
Testcase

Run checks the testcases above (3 examples, or your own). Submit also runs 20 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.

Solutions

Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.

ApproachTimeSpace
Brute force (search outward)O(10^(L/2) · L)O(L)
Optimal (mirror the left half)O(L)O(L)

1Brute force (search outward)

TimeO(10^(L/2) · L)The nearest palindrome can be about 10^(L/2) away for an L-digit number, and each check reads L digits.
SpaceO(L)The digit string built for each palindrome check.

Check numbers at distance 1, 2, 3, … from n, looking below before above, and return the first palindrome found. Checking below first makes the smaller value win ties.

  1. Parse n into a 64-bit number x.
  2. For d = 1, 2, 3, …: if x - d >= 0 and x - d is a palindrome, return it.
  3. Otherwise, if x + d is a palindrome, return it.
class Solution {
    public String nearestPalindromic(String n) {
        long x = Long.parseLong(n);
        for (long d = 1; ; d++) {
            if (x - d >= 0 && isPal(x - d)) return String.valueOf(x - d);
            if (isPal(x + d)) return String.valueOf(x + d);
        }
    }

    private boolean isPal(long v) {
        String s = String.valueOf(v);
        for (int i = 0, j = s.length() - 1; i < j; i++, j--) {
            if (s.charAt(i) != s.charAt(j)) return false;
        }
        return true;
    }
}

2Optimal (mirror the left half)

TimeO(L)Five candidates, each built and compared in O(L).
SpaceO(L)The strings used to build the mirrored candidates.

The closest palindrome keeps n's left half, or nudges it by one. Take the first ceil(L / 2) digits as prefix, and mirror prefix - 1, prefix and prefix + 1 onto the right (dropping the middle digit for odd L). When a nudge changes the prefix's length the result has a different number of digits, and those cases are covered by two fixed candidates: 99…9 with L - 1 digits and 10…01 with L + 1 digits. Return the candidate closest to n, other than n itself, preferring the smaller on ties.

  1. Let L = n.length and x = the value of n.
  2. Add candidates 10^(L - 1) - 1 and 10^L + 1.
  3. Let prefix = the first (L + 1) / 2 digits. For p in {prefix - 1, prefix, prefix + 1} with the same number of digits as prefix, mirror p into a palindrome of length L and add it.
  4. Skip any candidate equal to x; pick the smallest |c - x|, breaking ties by the smaller c.
class Solution {
    public String nearestPalindromic(String n) {
        int len = n.length();
        long x = Long.parseLong(n);
        List<Long> cands = new ArrayList<>();
        cands.add(pow10(len - 1) - 1);
        cands.add(pow10(len) + 1);
        String half = n.substring(0, (len + 1) / 2);
        long prefix = Long.parseLong(half);
        for (long p = prefix - 1; p <= prefix + 1; p++) {
            String s = String.valueOf(p);
            if (s.length() != half.length()) continue;
            StringBuilder rev = new StringBuilder(s).reverse();
            if (len % 2 == 1) rev.deleteCharAt(0);
            cands.add(Long.parseLong(s + rev));
        }
        long best = -1;
        for (long c : cands) {
            if (c == x || c < 0) continue;
            long dc = Math.abs(c - x), db = Math.abs(best - x);
            if (best == -1 || dc < db || (dc == db && c < best)) best = c;
        }
        return String.valueOf(best);
    }

    private long pow10(int k) {
        long v = 1;
        for (int i = 0; i < k; i++) v *= 10;
        return v;
    }
}

Edge cases to test

  • n is itself a palindrome: it does not count, so look for the next best one
  • Powers of ten like 1000: the answer 999 has one digit fewer
  • All nines like 999: the answer 1001 has one digit more
  • Ties: 12321 is 100 away from both 12221 and 12421, so return 12221
  • 18-digit inputs need 64-bit arithmetic (or BigInt in JavaScript)

Hints

Hint 1

A palindrome is decided by its first half. Copying the left half of n onto the right half gives a palindrome that is usually very close to n.

Hint 2

Close palindromes come from the left half, the left half + 1, and the left half - 1, each mirrored. Which other candidates appear when the number of digits changes?

Hint 3

Add 10^(len - 1) - 1 (all nines, one digit fewer) and 10^len + 1 (one digit more). Pick the closest candidate that is not n itself, preferring the smaller value on a tie.

FAQ

What is the best time complexity for Find the Closest Palindrome?

Optimal (mirror the left half) runs in O(L) time and O(L) extra space. Five candidates, each built and compared in O(L).

Which pattern does Find the Closest Palindrome use?

It is a arrays & hashing problem that uses the candidate generation pattern. Other problems with the same pattern: Minimize Result by Adding Parentheses to Expression.

Is there a brute force solution for Find the Closest Palindrome?

Yes. Brute force (search outward) takes O(10^(L/2) · L) time and O(L) space. Check numbers at distance 1, 2, 3, … from n, looking below before above, and return the first palindrome found.

Which edge cases should I test for Find the Closest Palindrome?

n is itself a palindrome: it does not count, so look for the next best one; Powers of ten like 1000: the answer 999 has one digit fewer; All nines like 999: the answer 1001 has one digit more; Ties: 12321 is 100 away from both 12221 and 12421, so return 12221; 18-digit inputs need 64-bit arithmetic (or BigInt in JavaScript).