O(log n) Java, 1 line O(log(n) + k) Ruby


  • 26

    I binary-search for where the resulting elements start in the array. It's the first index i so that arr[i] is better than arr[i+k] (with "better" meaning closer to or equally close to x). Then I just return the k elements starting there.

    def find_closest_elements(arr, k, x)
      arr[(0..arr.size).bsearch { |i| x - arr[i] <= (arr[i+k] || 1/0.0) - x }, k]
    end
    

    I think that's simpler than binary-searching for x and then expanding to the left and to the right like I've seen in other binary search solutions.


    Here's a Java version without using the library's binary search:

    public List<Integer> findClosestElements(List<Integer> arr, int k, int x) {
        int lo = 0, hi = arr.size() - k;
        while (lo < hi) {
            int mid = (lo + hi) / 2;
            if (x - arr.get(mid) > arr.get(mid+k) - x)
                lo = mid + 1;
            else
                hi = mid;
        }
        return arr.subList(lo, lo + k);
    }
    

    The binary search costs O(log n) (actually also just O(log (n-k)) and the subList call probably only takes O(1). As @sagimann pointed out, subList returns a view, not a separate copy. So it should only take O(1). Can be seen for example in ArrayList's subList and the SubList constructor it calls. I also checked LinkedList, it gets its subList method inherited from AbstractList, where it also takes only O(1). And AbstractList is a basis for most lists.

    Edit: I also implemented it in Go now, to make it O(log n). Edit 2: Ha, didn't have to do that, as the Java version apparently already was O(log n) (I didn't originally know Java returns a view, only added that now). Edit 3: Lol, I had mistakenly written "Python" in the title instead of "Ruby" but apparently nobody noticed (and it's at 1800 views). Fixed that now.


  • 0
    C
    This post is deleted!

  • 2
    C

    @StefanPochmann Brilliant & Elegant way!
    I trans it into c++ way:

    vector<int> findClosestElements(vector<int>& arr, int k, int x) {
        int left = 0;
        int right = arr.size()-k;
        while(left<right){
            int mid = left+(right-left)/2;
            if(x-arr[mid]>arr[mid+k]-x){
                left = mid+1;
            }else{
                right = mid;
            }
        }
        auto S = arr.begin()+left;
        auto E = arr.begin()+left+k;
        
        return vector<int>(S,E);
    }

  • 1

    The java binary search solution is very impressive.


  • 0
    L

    @StefanPochmann Truely bravo,


  • 0
    L

    Fantastic solution! For those who might be confused on why/how that binary search solution works, here is a link that might be helpful (one of the best treatments on binary search I have seen so far). It was helpful to me. https://www.topcoder.com/community/data-science/data-science-tutorials/binary-search/


  • 0
    C

    This solution is really nice.


  • 0
    J

    Sorry, it's really hard to understand why the first i satisfying arr[i] is better than arr[i+k] is the i we want. Can you explain in detail why this termination condition works? Thank you.


  • 2

    @jiaqi13

    arr[i] and arr[i+k] are the only difference between the window arr[i:i+k] and the window arr[(i+1):(i+1)+k] one position further right. So that's actually testing which of those two windows is better.

    "arr[i] is better than arr[i+k]" makes sure the window is right enough, and "first i" makes sure the window is left enough.


  • 0
    L

    I've read the link @LD_prettygood provided. but I still don't understand why this binary search works?

    @StefanPochmann I believe many of us have the same question. Could you please explain it?


  • 0
    W

    @LeoShi I think the main idea here is try our best to make x in the center of the window [i, i + k]. Intuitively, that also corresponds to the definition of closest in the problem.


  • 0

    @StefanPochmann Hey Stefan, fantastic!
    I am still confused about the explanation on choosing which "window is better".
    For the 2 windows : arr[i:i+k] and arr[(i+1):(i+1)+k], let we define
    d1 = max(abs(target - arr[i]), abs(target - arr[i+k-1]))
    d2 = max(abs(target - arr[i+1]), abs(target - arr[i+k]))

    I think the way to choose a "better window" is to choose the minimum (d1, d2), i.e the window with maximum distance towards target should be minimum. But this is wrong.

    Could you explain more about your solution on how to decide "which window is better"?
    Thanks!

    I always learn a lot from you :)


Log in to reply
 

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