# Java short O(NlogN) solution and O(logN + k) solution

• O(NlogN) solution:
The idea here is to simply sort the array based on the distance to the target and grab the top k elements.

``````public static List<Integer> findClosestElements(List<Integer> arr, int k, int x) {
arr.sort(Comparator.comparingInt(i -> Math.abs(i - x)));
arr = arr.subList(0, k);
arr.sort(Comparator.naturalOrder());
return arr;
}
``````

O(logN + k) solution:
We use binary search to find the nearest location of x in the array. This is logN.
Then we expand on both sides using 2 pointers, to get the k nearest elements.

``````    public static List<Integer> findClosestElements2(List<Integer> arr, int k, int x) {
if(x < arr.get(0)) return arr.subList(0, k);
if(x > arr.get(arr.size()-1)) return arr.subList(arr.size()-k+1, arr.size());

List<Integer> result = new ArrayList<>();
int index = binSearch(arr, x);
System.out.println(index);
int i = 0; int j = 0;
if(arr.get(index) == x) {
result.add(x);
i = index - 1;
j = index + 1;
} else {
i = index - 1;
j = index;
}

while(i >= 0 && j < arr.size() && result.size() != k) {
if(Math.abs(arr.get(i) - x) <= Math.abs(arr.get(j) - x)) {
result.add(0, arr.get(i--));
} else {
result.add(arr.get(j++));
}
}

if(result.size() == k) {
} else if(i < 0) {
result.addAll(arr.subList(j, j + k - result.size()));
} else {
result.addAll(0, arr.subList(i+1-k+result.size(), i+1));
}

return result;
}

public static int binSearch(List<Integer> a, int target) {
int st = 0;
int end = a.size() - 1;
int mid = 0;
while(st <= end) {
mid = (st + end)/2;
if(a.get(mid) == target) {
break;
} else if (a.get(mid) > target) {
end = mid -1;
} else {
st = mid +1;
}
}
return mid;
}

``````

• Thanks! Combined yours and @compton_scatter's solution.

``````public List<Integer> findClosestElements(List<Integer> arr, int k, int x) {
List<Integer> rst = new ArrayList<>();
int idx = Collections.binarySearch(arr, x);
idx = idx < 0 ? -(idx + 1) : idx;

int l = idx - 1, g = idx;
for (int i = 0; i < k; i++) {
if (l >= 0 && g < arr.size()) {
if (Math.abs(arr.get(l) - x) <= Math.abs(arr.get(g) - x)) {
rst.add(0, arr.get(l--));
} else {
rst.add(arr.get(g++));
}
} else if (l >= 0) {
rst.add(0, arr.get(l--));
} else {
rst.add(arr.get(g++));
}
}

return rst;
}
``````

• @haha2016 Nice, did not realize that Collections had binary search built in.

• Be careful to use BinarySearch when the input is List<> instead of ArrayList<>.
At least mention that to the interviewer.

If the input is LinkedList instead of ArrayList, binary Search will take O(NlogN) to find the target.

So, it's more safe to use a iterator here.

Same for the 2 pointers list.get() in the while loop(). To avoid O(kN) in the while loop, it's more safe to create a new ArrayList containing [xIndex-k, xIndex+k] elements first during the iteration.

• @LeetCoding Nice remarks!

• Same Idea: Binary Search + two pointers

``````    public List<Integer> findClosestElements(List<Integer> arr, int k, int x) {
int p = findInsertPos(arr,x);
//System.out.println(p);
List<Integer> res = new LinkedList<>();
int l = p - 1;
int r = p;
int count = 0;
while(l >= 0 && r < arr.size()&&count < k){
if(x-arr.get(l)>arr.get(r)-x){
count++;
r++;
}
else{
count++;
l--;
}
}
// System.out.println(l);
// System.out.println(r);
//  System.out.println(count);
while(l >= 0&&count < k){
l--;
count++;
}
while(r < arr.size()&&count < k){
r++;
count++;
}
//System.out.println(l);
//System.out.println(r);
for(int i = l + 1;i < r;i++){
res.add(arr.get(i));
}
return res;
}
private int findInsertPos(List<Integer> arr,int x){
int left = 0;
int right = arr.size() - 1;
while(left <= right){
int mid = left + (right - left)/2;
if(arr.get(mid) < x){
left = mid + 1;
}
else{
right = mid - 1;
}
}
return left;
}
}``````

• Hi, can you explain the logic of this line of code:
result.addAll(0, arr.subList(i+1-k+result.size(), i+1));

@johnyrufus16

• @tigermlt You need k elements in result. and in this statement we are extracting the remaining elements to the left of i and adding them to the front of the result.
The way I arrived at the start and end of the sublist is as follows:

sizeNeeded to extract = k - result.size() // remaining k elements. ---> A
end = i + 1. // we need elements up to and including i. ----> C

start = ?

we know that sizeNeeded to extract can also be written as = end - start ---> B

combining A and B, we get

k - result.size() = end - start
start = end - k + result.size()

substituting end from C we get

start = i + 1 - k + result.size()

These are the start and end values of the sublist I have used.

• @johnyrufus16 thanks!

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.