# Solution For Find K Closest Elements

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 two-pointer 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 two-pointer technique to expand the subarray to find the k closest elements.

Algorithm:

1. 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]).

2. Two-pointer 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 i-1 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.

3. 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]
``````

## Step by Step Implementation For Find K Closest Elements

```Given a sorted array, two integers k and x, find the k closest elements to x in the array. The result should also be sorted in ascending order. If there is a tie, the smaller elements are always preferred.

/*

Solution:

We can use a binary search approach to find the index of the element closest to x.

Once we have that, we can use a two pointer approach to find the k closest elements.

We start one pointer at the index of the element closest to x and the other pointer at index+1.

We then keep track of the k closest elements found so far.

We compare the elements pointed to by the two pointers and add the smaller element to our result.

We then move the pointer that points to the smaller element.

We keep doing this until we find k closest elements.

*/

public List findClosestElements(int[] arr, int k, int x) {

// find the index of the element closest to x
int index = binarySearch(arr, x);

// use two pointer approach to find k closest elements
int left = index;
int right = index+1;

// keep track of the k closest elements found so far
List result = new ArrayList<>();

// add the element at index to the result

// find the k closest elements
while(result.size() < k) {

// compare the elements pointed to by the two pointers
// and add the smaller element to the result
if(left >= 0 && right < arr.length) {
if(Math.abs(arr[left] - x) <= Math.abs(arr[right] - x)) {
left--;
}
else {
right++;
}
}
// if we have reached the end of the array,
// we can just add the remaining elements from the other side
else if(left >= 0) {
left--;
}
else {
right++;
}
}

// sort the result in ascending order and return
Collections.sort(result);
return result;
}

// binary search function
public int binarySearch(int[] arr, int x) {
int left = 0;
int right = arr.length - 1;

while(left <= right) {
int mid = left + (right - left) / 2;

if(arr[mid] == x) {
return mid;
}
else if(arr[mid] < x) {
left = mid + 1;
}
else {
right = mid - 1;
}
}

// if no exact match is found,
// we return the index of the element closest to x
return left;
}```
```def findClosestElements(arr, k, x):

n = len(arr)

# if x is present in arr, then find the index
# of it
if x in arr:
index = arr.index(x)
else:

# if x is not present then do binary search
# to find the ceiling of x
index = bisect.bisect_left(arr, x)

# print index
left = index - 1

# right index
right = index + 1

# number of elements to be returned
count = k

# result list
result = []

# add elements on left of index
# to the result
while left >= 0 and count > 0:
result.append(arr[left])
left -= 1
count -= 1

# add elements on right of index
# to the result
while right < n and count > 0:
result.append(arr[right])
right += 1
count -= 1

# sort the result
result.sort()

# return the result
return result```
```var findKClosestElements = function(arr, k, x) {
};```
```vector findClosestElements(vector& arr, int k, int x) {
// Initialize a max heap
priority_queue, vector>, greater>> pq;

// Iterate through the array and push the elements into the max heap
for(int i = 0; i < arr.size(); i++) {
pq.push({abs(arr[i] - x), arr[i]});
}

// Initialize an empty vector to store the k closest elements
vector res;

// Pop the top k elements from the heap and push them into the vector
for(int i = 0; i < k; i++) {
res.push_back(pq.top().second);
pq.pop();
}

// Return the vector
return res;
}```
```using System;
using System.Collections.Generic;
using System.Linq;

public class Solution {
public IList FindClosestElements(int[] arr, int k, int x) {
// create a min heap to store the k closest elements
// to x
PriorityQueue minHeap = new PriorityQueue(k,
new Comparator() {
public int Compare(int a, int b) {
if (Math.Abs(a-x) == Math.Abs(b-x))
return a - b;
return Math.Abs(a-x) - Math.Abs(b-x);
}
});

// go through the array and add elements to the heap
// if they are closer to x than the elements currently
// in the heap
for (int i = 0; i < arr.length; i++) {
if (i < k)
else {
if (Math.Abs(arr[i]-x) < Math.Abs(minHeap.Peek()-x)) {
minHeap.Poll();
}
}
}

// convert the heap to a list
List result = new List();
while (minHeap.size() > 0)

// sort the list
Collections.Sort(result);
return result;
}
}```

Scroll to Top

## Top 100 Leetcode Practice Problems In Java

Get 30% Off Instantly!
[gravityforms id="5" description="false" titla="false" ajax="true"]