Best of three || O(1) space || no need of list of all palindromes
Intuition\nSuppose med = median(nums)\nThe best choice of y is one among these three:\n1. med(only if med itself is a palindromic num), \n2. leftmostPal(med): B
# Intuition\nSuppose med = `median(nums)`\nThe best choice of `y` is one among these three:\n1. `med`(only if med itself is a palindromic num), \n2. `leftmostPal(med)`: Biggest num < med which is palindromic.\n3. `rightmostPal(med)`: Smallest num > med which is palindromic.\n# Implementation\nTwo `while` loops will do our task. We now just have to check which one of these two or three give us the minimum cost. Implementations can vary, I am attaching mine here below \n\n# Complexity\n- Time complexity: $O(nlogn)$ \nfor sorting the array for finding median.\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: $O(1)$ \nnothing new creating whose space can vary based on n\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```python\nclass Solution:\n    def minimumCost(self, nums: List[int]) -> int:\n        n, cost = len(nums), lambda x : sum([abs(x-a) for a in nums])\n        \n        #1. Find median\n        nums.sort()\n        med = nums[n//2]\n        left, right = med-1, med+1\n        \n        #2. leftmostPal(med)\n        while str(left) != str(left)[::-1]:\n            left -= 1\n\n        #3. rightmostPal(med)\n        while str(right) != str(right)[::-1]:\n            right += 1\n        \n        res = [left, right]\n\n        #4. Add med to res if med is a palrome\n        if str(med) == str(med)[::-1]:\n            res.append(med)\n\n        #5. find the minimum choice, based on what cost they generate\n        best = min(res, key = cost)\n\n        #6. return the cost of the best choice\n        return cost(best)\n```\n\n\n\n\n
['Python3']