3 different approaches in Python, with explanation
First approach - Sorting by absolute difference and taking the first k elements. This approach does not scale well and only works because the input is small.\n\
**First approach** - Sorting by absolute difference and taking the first k elements. This approach does not scale well and only works because the input is small.\n\n```\nclass Solution(object):\n    def findClosestElements(self, arr, k, x):\n        # Time: O(n.lgn + k.lgk)\n        # Space: O(n + k)\n        return sorted(sorted(arr, key=lambda val: abs(val - x))[:k])\n\n```\n\n**Second approach** - Two pointers approach but without any binary search performed on the original array. This approach does not make use of the sorted property of the input array. We use a `Counter` to track how many of each value in the array. The two pointers here essentially are the lower and upper values in the final result. We decrement the lower pointer and increment the upper pointer and add the count of the values into the result until the total length of the result exceeds k. This approach works for arrays where elements have a relatively small absolute difference.\n\n```\nclass Solution(object):\n    def findClosestElements(self, arr, k, x):\n        # Time: O(n + k.lgk)\n        # Space: O(n + k)\n        from collections import Counter\n        c = Counter(arr)\n        res = []\n        lower, upper = x - 1, x\n        min_val, max_val = min(arr), max(arr)\n        if x in c:\n            res.extend([x] * c[x])\n            upper += 1\n        while len(res) < k:\n            while lower >= min_val and lower not in c:\n                lower -= 1\n            while upper <= max_val and upper not in c:\n                upper += 1\n            if abs(x - lower) <= abs(x - upper):\n                res.extend([lower] * min(k - len(res), c[lower]))\n                lower -= 1\n            else:\n                res.extend([upper] * min(k - len(res), c[upper]))\n                upper += 1\n        return sorted(res)[:k]\n```\n\n**Third approach** - Use binary search to find the value's position in the array, and expand outwards using two pointers. This approach scales the best.\n\n```\nclass Solution(object):\n    def findClosestElements(self, arr, k, x):\n        # Time: O(lgn + k)\n        # Space: O(k)\n        import bisect\n        index = min(bisect.bisect_left(arr, x), len(arr) - 1)\n        left, right = index - 1, index + 1 if arr[index] == x else index\n        while right - left < k + 1:\n            if left >= 0 and (right >= len(arr) or abs(arr[left] - x) <= abs(arr[right] - x)):\n                left -= 1\n            else:\n                right += 1\n        return arr[left + 1:right]\n\n```
[]