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


  • 2

    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;
        }
    
    

  • 2
    H

    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;
        }
    

  • 0

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


  • 1

    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.


  • 0
    H

    @LeetCoding Nice remarks!


  • 1
    Y

    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;
        }
    }

  • 0
    T

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

    @johnyrufus16


  • 1

    @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.


  • 0
    T

    @johnyrufus16 thanks!


Log in to reply
 

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