Warning
There is a cleaner solution, but that solution is quite difficult to understand. Neetcode made a video on it.
Intuition
- Whenever an array is sorted, think Binary Search.
- Need to use Bisect Left since if there is a tie, then pick the smaller within a and b.
Complexity
Runtime
Space
Code
Without Manual Array Sort
import bisect
class Solution:
def findClosestElements(self, arr: List[int], k: int, x: int) -> List[int]:
n = len(arr)
x_idx = bisect.bisect_left(arr, x)
left, right = x_idx - 1, x_idx
while left >= 0 and right < n and k > 0:
a, b = arr[left], arr[right]
if abs(a - x) == abs(b - x):
if a < b:
left -= 1
else:
right += 1
elif abs(a - x) < abs(b - x):
left -= 1
else:
right += 1
k -= 1
while k > 0:
if left >= 0:
a = arr[left]
left -= 1
else:
b = arr[right]
right += 1
k -= 1
return arr[left + 1 : right]Bisect Left with Manual Array Sort
import bisect
class Solution:
def findClosestElements(self, arr: List[int], k: int, x: int) -> List[int]:
n = len(arr)
x_idx = bisect.bisect_left(arr, x)
left, right = x_idx - 1, x_idx
res = []
while left >= 0 and right < n and k > 0:
a, b = arr[left], arr[right]
if abs(a - x) == abs(b - x):
if a < b:
res.append(a)
else:
res.append(b)
elif abs(a - x) < abs(b - x):
res.append(a)
else:
res.append(b)
if res[-1] == a:
left -= 1
else:
right += 1
k -= 1
while k > 0:
if left >= 0:
a = arr[left]
res.append(a)
left -= 1
else:
b = arr[right]
res.append(b)
right += 1
k -= 1
return sorted(res)Custom Sort Operator
class Solution:
def findClosestElements(self, arr: List[int], k: int, x: int) -> List[int]:
res = []
sorted_arr = sorted(arr, key = lambda num: abs(x - num))
for i in range(k):
res.append(sorted_arr[i])
return sorted(res)