O(nlgn): Each Number Generates 3 Palindromes
IntuitionLet each number generate 3 palindromes: its nearest palindrome pal, pal's prev palindrome, and pal's next palindrome. We can obtain totally 3n candidat
# Intuition
Let each number generate 3 palindromes: its nearest palindrome pal, pal's prev palindrome, and pal's next palindrome. We can obtain totally 3n candidate palindromes, and the best one to minimize cost must be among them.
# Approach
1. Generate 3n candidate palindromes.
2. Sort the array.
3. Build a prefix sum array and a suffix array, and use binary search ith them to achieve O(lgn) time for getting an outcome of cost with each candidate palindrome.
4. Choose the best cost outcome as result.
# Complexity
- Time complexity:
O(nlgn)
- Space complexity:
O(n)
# Code
```javascript []
/**
 * @param {number[]} nums
 * @return {number}
 */
var minimumCost = function(nums) {
    const len = nums.length
    nums.sort((a, b) => a - b)

    const sumFL = new Array(len), sumFR = new Array(1 + len)
    sumFL[-1] = sumFR[len] = 0
    for (let i = 0; i < len; i++)
        sumFL[i] = nums[i] + sumFL[i - 1]
    for (let i = len - 1; i > -1; i--)
        sumFR[i] = nums[i] + sumFR[i + 1]
    const sum = sumFL.at(-1)

    function getOutcome(val) {
        let low = 0, high = len - 1
        // find earliest high where
        // nums[high] > val
        if (nums[high] <= val) {
            return val * len - sum
        }
        while (low < high) {
            const mid = (low + high) >> 1
            if (nums[mid] > val)    high = mid
            else low = mid + 1
        }
        
        const resultFL = val * high - sumFL[high - 1]
        const resultFR = sumFR[high] - val * (len - high)
        return resultFL + resultFR
    }


    function getPal(val) {
        const str = String(val)
        const size = str.length
        const half = size >> 1
        const mid = (size & 1) ? str[half] : ''

        const leading = str.slice(0, half)
        const pal = leading + mid + [...leading].reverse().join('')

        return Number(pal)
    }
    function toPrevPal(pal) {
        const str = String(pal)
        const size = str.length
        const half = size >> 1

        let leading = Number(str.slice(0, size - half))
        if (String(leading - 1).length < String(leading).length) {
            return 10 ** (size - 1) - 1
        }

        leading--
        return getPal(Number(String(leading) + str.slice(-half)))
    }
    function toNextPal(pal) {
        const str = String(pal)
        const size = str.length
        const half = size >> 1

        let leading = Number(str.slice(0, size - half))
        if (String(leading + 1).length > String(leading).length) {
            return 10 ** size + 1
        }
        leading++
        return getPal(Number(String(leading) + str.slice(-half)))
    }

    
    let result = Infinity
    for (const val of nums) {
        const pal = getPal(val)
        result = Math.min(
            result, 
            getOutcome(toPrevPal(pal)),
            getOutcome(pal),
            getOutcome(toNextPal(pal)),
        )
    }


    return result
};
```
In fact, we only need to consider the 6 palindromes around the (at most 2) medians. So the code can be optimized to:
# Code
```javascript []
/**
 * @param {number[]} nums
 * @return {number}
 */
var minimumCost = function(nums) {
    const len = nums.length
    nums.sort((a, b) => a - b)

    const sumFL = new Array(len), sumFR = new Array(1 + len)
    sumFL[-1] = sumFR[len] = 0
    for (let i = 0; i < len; i++)
        sumFL[i] = nums[i] + sumFL[i - 1]
    for (let i = len - 1; i > -1; i--)
        sumFR[i] = nums[i] + sumFR[i + 1]
    const sum = sumFL.at(-1)

    function getOutcome(val) {
        let low = 0, high = len - 1
        // find earliest high where
        // nums[high] > val
        if (nums[high] <= val) {
            return val * len - sum
        }
        while (low < high) {
            const mid = (low + high) >> 1
            if (nums[mid] > val)    high = mid
            else low = mid + 1
        }
        
        const resultFL = val * high - sumFL[high - 1]
        const resultFR = sumFR[high] - val * (len - high)
        return resultFL + resultFR
    }


    function getPal(val) {
        const str = String(val)
        const size = str.length
        const half = size >> 1
        const mid = (size & 1) ? str[half] : ''

        const leading = str.slice(0, half)
        const pal = leading + mid + [...leading].reverse().join('')

        return Number(pal)
    }
    function toPrevPal(pal) {
        const str = String(pal)
        const size = str.length
        const half = size >> 1

        let leading = Number(str.slice(0, size - half))
        if (String(leading - 1).length < String(leading).length) {
            return 10 ** (size - 1) - 1
        }

        leading--
        return getPal(Number(String(leading) + str.slice(-half)))
    }
    function toNextPal(pal) {
        const str = String(pal)
        const size = str.length
        const half = size >> 1

        let leading = Number(str.slice(0, size - half))
        if (String(leading + 1).length > String(leading).length) {
            return 10 ** size + 1
        }
        leading++
        return getPal(Number(String(leading) + str.slice(-half)))
    }

    
    let result = Infinity
    const mIndex = len >> 1
    const candidates = [nums[mIndex]]
    if ((len & 1) && len >= 2)  candidates.push(nums[mIndex - 1])   
    for (const val of candidates) {
        const pal = getPal(val)
        result = Math.min(
            result, 
            getOutcome(toPrevPal(pal)),
            getOutcome(pal),
            getOutcome(toNextPal(pal)),
        )
    }


    return result
};
```
['JavaScript']