0658. Find K Closest Elements

Medium

Given a sorted integer array arr, two integers k and x, return the k closest integers to x in the array. The result should also be sorted in ascending order.

An integer a is closer to x than an integer b if:

|a - x| < |b - x|, or
|a - x| == |b - x| and a < b

Example 1:

Input: arr = [1,2,3,4,5], k = 4, x = 3
Output: [1,2,3,4]

Example 2:

Input: arr = [1,2,3,4,5], k = 4, x = -1
Output: [1,2,3,4]

Constraints:

1 <= k <= arr.length
1 <= arr.length <= 10⁴
arr is sorted in ascending order.
-10⁴ <= arr[i], x <= 10⁴

 class Solution:
    def findClosestElements(self, arr: List[int], k: int, x: int) -> List[int]:


        # Binary Search To Find The Left Bound


        left = 0
        right = len(arr)-k

        while left < right:
            mid = (left+right)//2

            #if abs(arr[mid]-x) < abs(arr[mid+k]-x):
            if x - arr[mid] <= arr[mid + k] - x:
                right = mid
            else:
                left = mid + 1

        return arr[left: left+k]




#         arr_l = len(arr)

#         if arr_l == k:
#             return arr


#         left = self.search_closest(arr, x)
#         #left = bisect_left(arr, x) - 1

#         # print(left)
#         # print("closest_position", closest_position, arr[closest_position])

#         right = left + 1

#         while right - left - 1 < k:
#             if left == -1:
#                 right += 1
#                 continue

#             if right == len(arr) or abs(arr[left] - x) <= abs(arr[right] - x):
#                 left -= 1
#             else:
#                 right += 1

#         # Return the window
#         return arr[left + 1:right]




#     def search_closest(self, nums, target):

#         l, r = 0, len(nums)-1

#         if nums[l] >= target:
#             return l
#         if nums[r] <= target:
#             return r

#         while l <= r:
#             mid = l + (r-l)//2

#             if nums[mid] == target:
#                 return mid
#             if nums[mid] < target and nums[mid+1] > target:
#                 return mid if (target-nums[mid]) <= (nums[mid+1]-target) else mid+1
#             elif nums[mid] < target:
#                 l = mid
#             else:
#                 r = mid

0658. Find K Closest Elements

Random Note