Similar Problems
Similar Problems not available
Find K Closest Elements  Leetcode Solution
LeetCode: Find K Closest Elements Leetcode Solution
Difficulty: Medium
Topics: binarysearch slidingwindow twopointers heappriorityqueue array sorting
Problem statement:
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.
Constraints: 1 <= k <= arr.length 1 <= arr.length <= 10^4 Arr is sorted in ascending order. 10^4 <= arr[i], x <= 10^4
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]
Solution:
Approach: The given array is sorted and the task is to find the k closest elements. We can apply binary search to find the position of the element x and use twopointer technique to expand the subarray to find the k closest elements. In order to use binary search, we need to find the position of x in the given array. We can use binary search to find the position. Once we know the position of x, we can use twopointer technique to expand the subarray to find the k closest elements.
Algorithm:

Binary search: We use binary search to find the index of x in the sorted array. If x is already present in the array, we can directly return the subarray of length k centered around it. Otherwise, we find the index i such that (arr[i] <= x < arr[i+1]).

Twopointer technique: We use two pointers, left and right, to expand the subarray of length k centered around x. Initially, left and right point to index i1 and i respectively. We move left pointer to the left and right pointer to the right until we have k elements in the subarray. The condition for moving the pointers is that if the distance of arr[left] and x is less than or equal to the distance of arr[right] and x, then move left pointer to the left, otherwise move right pointer to the right.

Return the subarray: Finally, we return the subarray of length k centered around x.
Let's see the Python code implementation:
class Solution: def findClosestElements(self, arr: List[int], k: int, x: int) > List[int]: # Binary Search to find the index of x in arr left, right = 0, len(arr)  1 while left < right: mid = (left + right) // 2 if arr[mid] < x: left = mid + 1 else: right = mid
# left is the index of x in arr or the index of the element closest to x from the left
# We expand the subarray in both directions to find the k closest elements
left_ptr, right_ptr = left  1, left
while k > 0:
if left_ptr < 0:
right_ptr += 1
elif right_ptr >= len(arr):
left_ptr = 1
elif x  arr[left_ptr] <= arr[right_ptr]  x:
left_ptr = 1
else:
right_ptr += 1
k = 1
return arr[left_ptr+1:right_ptr]
Find K Closest Elements Solution Code
1