Find K Closest Elements

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]

Approach

Java

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;

public class FindKClosestElements {
    public static void main(String[] args) {
        int[] arr = { 1, 2, 3, 4, 5 };
        int k = 4, x = 3;
        List<Integer> closest = findClosestElements(arr, k, x);
        System.out.println(Arrays.asList(closest));
    }

    static List<Integer> findClosestElements(int[] arr, int k, int x) {
        List<Integer> res = new ArrayList<Integer>();
        int n = arr.length;
        for (int i = 0; i < k; i++) {
            res.add(arr[i]);
        }
        for (int i = k; i < n; i++) {
            if (Math.abs(res.get(0) - x) > Math.abs(arr[i] - x)) {
                res.remove(0);
                res.add(arr[i]);
            }
        }
        Collections.sort(res);
        return res;
    }

}

C++

#include <bits/stdc++.h>
using namespace std;

vector<int> findClosestElements(vector<int>& arr, int k, int x) 
{
          vector<int> res;
        int n=arr.size();
            for(int i=0;i<k;i++)
            {
                res.push_back(arr[i]);
            }
            for(int i=k;i<n;i++)
            {
                if(abs(res[0]-x)>abs(arr[i]-x))
                {
                    res.erase(res.begin());
                    res.push_back(arr[i]);
                }                       
            }
        sort(res.begin(),res.end());
        return res;
}

int main()
{
    vector<int> arr ={1,2,3,4,5};
    int k = 4, x = 3;
    vector<int> closest=findClosestElements(arr,k,x);
    for(int i=0;i<closest.size();i++)
       cout<<closest[i]<<" ";
    return 0;
}