Next palindromic number I wrote a function that takes a number and finds the next palindromic number. Time complexity is currently O(n2), which is really bad. How could one make this function more efficient? 

function nextPalindrome(n) {
  // first we create a function to check if a single number is a palindrome
  function isPalindrome(num) {
    const forward = num.toString();
    let backward = [];
    for (let i = forward.length - 1; i &gt;= 0; i--) {
      backward.push(forward[i]);
    }
    backward = backward.join('');
    return forward === backward;
  }
  // now let's create a counter variable to increment our number (n)
  // we'll initialize it as n + 1 since we know we're not going to check the first number
  let countUp = n + 1;
  // we also need a nextPalindrome variable
  let nextP;
  // now we need to begin some sort of loop
  // perhaps a while loop will do
  while (true) {
    if (isPalindrome(countUp)) {
      return countUp;
    } else {
      countUp += 1;
    }
  }

}
Note: Minor change to the algorithm after I found a scenario it didn't cover

This is more of a mathematical problem than a programming one. After some thinking and experimentation, I've come up with an algorithm that can solve this in O(n), where n is the number of digits in the starting number. The basic principle is that we first break down the number into an array of digits, then start at the two ends and work our way inward to the middle, trying to set each pair of digits to the lower one, or as close to the lower one, in as many places as possible.

When examining a pair of digits, we always override the lower-order digit with the higher-order one. If the lower-order digit is greater than the higher-order one, it means the value of our number has reduced as a result of the override, so we set a carry flag. This carry flag will cause the next digit we measured from the lower end of the number (i.e. the lower-order one if we're less than halfway through the number, and the higher-order one if we're more than halfway through) to increment by one before the override is made. If this incrementation causes the digit to "overflow" into 10, we immediately set the digit to 0, set the carry flag to true, and proceed to the next digit.

function nextPalindrome(n) {
    let digits = [];
    let m = n;
    while (m &gt; 0) {
        digits.unshift(m % 10);
        m = Math.trunc(m / 10);
    }

    let carryFlag = false;
    let midPoint = Math.floor(digits.length / 2);

    for (let i = 0; i &lt; digits.length; i++) {
        let copyFrom = digits[i];
        let copyTo = digits[digits.length - 1 - i] + carryFlag;
        if (copyTo === 10) {
            digits[digits.length - 1 - i] = 0;
            carryFlag = true;
        }
        else {
            let digit = (i &lt; midPoint) ? copyFrom : copyTo;
            carryFlag = copyTo &gt; digit;
            digits[i] = digits[digits.length - 1 - i] = digit;
        }
    }

    return digits.reduce((acc, next) =&gt; 10 * acc + next, 0);
}


I don't have a pure mathematical proof detailed, but it seems to work. Please feel free to test it (especially with edge cases) and comment if something's wrong.