# Java 4-Liner and O(n) Time Solution

• O(nlog(n)) Time Solution:

``````public List<Integer> findClosestElements(List<Integer> arr, int k, int x) {
Collections.sort(arr, (a,b) -> a == b ? a - b : Math.abs(a-x) - Math.abs(b-x));
arr = arr.subList(0, k);
Collections.sort(arr);
return arr;
}
``````

O(n) Time Solution:

``````public List<Integer> findClosestElements(List<Integer> arr, int k, int x) {
List<Integer> less = new ArrayList<>(), greater = new ArrayList<>(),

for (Integer i : arr) {
}

Collections.reverse(less);
int  i = 0, j = 0, n = less.size(), m = greater.size();
for (int size=0;size<k;size++) {
if (i < n && j < m) {
if (Math.abs(less.get(i) - x) <= Math.abs(greater.get(j) - x)) lessResult.add(less.get(i++));
}
else if (i < n) lessResult.add(less.get(i++));
}

Collections.reverse(lessResult);
return lessResult;
}
``````

Note that above solution can be improved using binary search under the assumption that we have O(1) access to elements in input list.

• @compton_scatter Your first solution is very straight forward. Can I refer it in the editorial solution?

• @Mr.Bin Sure

• for (Integer i : arr) {
}

I think you can optimize here by using binary search since the original array is sorted :)

• @Mr.Bin The input elements were given as a list so I was not sure if I had O(1) access

• @compton_scatter Wow never thought of that!

• @compton_scatter Hoping :) they created an array list, O(1) then can be assumed

• Both are great ideas. The following are some simplifications to codes:

• `(a,b) -> a == b ? a - b : Math.abs(a-x) - Math.abs(b-x)` -> `Comparator.comparingInt(a -> Math.abs(a - x))`.

• `Math.abs(less.get(i) - x) <= Math.abs(greater.get(j) - x)` -> `x - less.get(i) <= greater.get(j) - x`.

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