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 – Solution in 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++){
            maxHeap.add(new Pair(arr[i],Math.abs(arr[i]-x)));
        }
        for(int i=k;i<arr.length;i++){
            
            if(maxHeap.peek().gap > Math.abs(arr[i]-x)){
                maxHeap.remove();
                maxHeap.add(new Pair(arr[i],Math.abs(arr[i]-x)));
            } else if(maxHeap.peek().gap == Math.abs(arr[i]-x)){
                if(maxHeap.peek().val > arr[i]){
                    maxHeap.remove();
                maxHeap.add(new Pair(arr[i],Math.abs(arr[i]-x)));
                }
            }
            
        }
        
        while(maxHeap.size() > 0){
            ans.add(maxHeap.peek().val);
            maxHeap.remove();
        }
        Collections.sort(ans);
        return ans;
    }
}

658. Find K Closest Elements – Solution in 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.