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

  • 20

    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]

    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;
                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
    This post is deleted!

  • 1

    @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;
            int mid = left+(right-left)/2;
                left = mid+1;
                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

    @StefanPochmann Truely bravo,

  • 0

    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

    This solution is really nice.

  • 0

    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.

  • 1


    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.

Log in to reply

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