Java 4-Liner and O(n) Time Solution


  • 14

    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<>(),
                      lessResult = new LinkedList<>(), greaterResult = new LinkedList<>();
     
        for (Integer i : arr) {
            if (i <= x) less.add(i);
            else greater.add(i);
        }
        
        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 greaterResult.add(greater.get(j++));
            }
            else if (i < n) lessResult.add(less.get(i++));
            else greaterResult.add(greater.get(j++));
        }
    
        Collections.reverse(lessResult);
        lessResult.addAll(greaterResult);
        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.


  • 0

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


  • 0

    @Mr.Bin Sure


  • 0

  • 0

    @compton_scatter said in Java 4-Liner and O(n) Time Solution:

    for (Integer i : arr) {
    if (i <= x) less.add(i);
    else greater.add(i);
    }

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


  • 1

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


  • 0

    @compton_scatter Wow never thought of that!


  • 0

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


  • 0

    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.


Log in to reply
 

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