# Find K Closest Elements – Leetcode Solution

In this post, we are going to solve the 658. Find K Closest Elements problem of Leetcode. This problem 658. Find K Closest Elements is a Leetcode medium level problem. Let’s see the code of the 658. Find K Closest Elements – Leetcode Solution.

## Problem

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 <= 104`
• `arr` is sorted in ascending order.
• `-104 <= arr[i], x <= 104`

Now, let’s see the leetcode solution of 658. Find K Closest Elements.

# Find K Closest Elements – Leetcode Solution

We are going to solve the problem using Priority Queue or Heap Data structure ( Max Heap ). Let’s see the solution.

### 658. Find K Closest Elements – Solutionin Java

```class Solution {

public class Pair implements Comparable<Pair>{

int val;
int gap;

Pair(){}

Pair(int val, int gap){
this.val = val;
this.gap = gap;
}

public int compareTo(Pair ob){
if(this.gap == ob.gap){
return this.val - ob.val;
} else{
return this.gap - ob.gap;
}
}

}

public List<Integer> findClosestElements(int[] arr, int k, int x) {
List<Integer> ans = new ArrayList<Integer>();
PriorityQueue<Pair> maxHeap = new PriorityQueue<Pair>(Collections.reverseOrder());

for(int i=0;i<k;i++){
}
for(int i=k;i<arr.length;i++){

if(maxHeap.peek().gap > Math.abs(arr[i]-x)){
maxHeap.remove();
} else if(maxHeap.peek().gap == Math.abs(arr[i]-x)){
if(maxHeap.peek().val > arr[i]){
maxHeap.remove();
}
}

}

while(maxHeap.size() > 0){
maxHeap.remove();
}
Collections.sort(ans);
return ans;
}
}```

## 658. Find K Closest Elements – Solutionin C++

```  vector<int> findClosestElements(vector<int>& arr, int k, int x) {

priority_queue<pair<int,int>> pq;

for(int i=0;i<arr.size();i++)
{pq.push({abs(arr[i]-x),arr[i]});
if(pq.size()>k)
pq.pop();
}
vector<int> ans;
while(pq.size()>0)
{
ans.push_back(pq.top().second);
pq.pop();
}
sort(ans.begin(),ans.end());
return ans;
}```

## 658. Find K Closest Elements – Solution in Python

```class Solution(object):
def findClosestElements(self, arr, k, x):
heap,res = [],[]
for i in arr:heap.append((abs(x-i),i))
heapq.heapify(heap)
for _ in range(k):res.append(heapq.heappop(heap)[1])
return sorted(res)```

Note: This problem 658. Find K Closest Elements is generated by Leetcode but the solution is provided by CodingBroz. This tutorial is only for Educational and Learning purpose.