Find K Closest Elements

Medium Binary Search Bisect Original on LeetCode

Find K Closest Elements is a medium binary search problem solved with the bisect pattern. The best approach, optimal (binary search on the window start), runs in O(log(n - k) + k) time and O(1) space. Below are 3 approaches in Java, Python, C++ and JavaScript, from brute force (sort by distance) up.

Problem

You are given a sorted integer array arr and two integers k and x. Return the k values of arr that are closest to x, listed in ascending order.

Value a is closer to x than value b when |a - x| < |b - x|. When the distances are equal, the smaller value counts as closer.

Examples

Example 1

Input
arr = [2, 5, 7, 8, 12, 15], k = 3, x = 9
Output
[7, 8, 12]
Why
Distances to 9 are 7, 4, 2, 1, 3, 6. The three smallest belong to 8, 12 and 7.

Example 2

Input
arr = [1, 3, 5, 7], k = 2, x = 4
Output
[3, 5]
Why
3 and 5 are both 1 away; 1 and 7 are 3 away.

Example 3

Input
arr = [10, 20, 30], k = 2, x = -5
Output
[10, 20]
Why
x is left of every value, so the first k elements are the closest.

Constraints

  • 1 <= k <= arr.length <= 10^4
  • arr is sorted in non-decreasing order.
  • -10^4 <= arr[i], x <= 10^4

Solve it here

Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.

00:00
Testcase

Run checks the testcases above (3 examples, or your own). Submit also runs 14 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.

Solutions

Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.

ApproachTimeSpace
Brute force (sort by distance)O(n log n)O(n)
Two pointers (shrink the window)O(n)O(1)
Optimal (binary search on the window start)O(log(n - k) + k)O(1)

1Brute force (sort by distance)

TimeO(n log n)A full sort of n values by distance.
SpaceO(n)The copied list.

Sort a copy of the values by distance to x, breaking ties by the smaller value, take the first k and sort those back into ascending order.

  1. Copy arr into a list.
  2. Sort by (|a - x|, a).
  3. Take the first k values, sort ascending, return.
class Solution {
    public List<Integer> findClosestElements(int[] arr, int k, int x) {
        List<Integer> all = new ArrayList<>();
        for (int a : arr) all.add(a);
        all.sort((a, b) -> Math.abs(a - x) != Math.abs(b - x) ? Math.abs(a - x) - Math.abs(b - x) : a - b);
        List<Integer> res = new ArrayList<>(all.subList(0, k));
        Collections.sort(res);
        return res;
    }
}

2Two pointers (shrink the window)

TimeO(n)n - k removals, each O(1).
SpaceO(1)Two indices, besides the output.

The answer is a window of the sorted array. Start with the whole array and, while it holds more than k elements, discard whichever end is farther from x (the right end on a tie, since the smaller value wins).

  1. lo = 0, hi = n - 1.
  2. While hi - lo + 1 > k: if x - arr[lo] <= arr[hi] - x, hi--; else lo++.
  3. Return arr[lo..hi].
class Solution {
    public List<Integer> findClosestElements(int[] arr, int k, int x) {
        int lo = 0, hi = arr.length - 1;
        while (hi - lo + 1 > k) {
            if (x - arr[lo] <= arr[hi] - x) hi--;
            else lo++;
        }
        List<Integer> res = new ArrayList<>();
        for (int i = lo; i <= hi; i++) res.add(arr[i]);
        return res;
    }
}

3Optimal (binary search on the window start)

TimeO(log(n - k) + k)Binary search over n - k + 1 starts, then k elements are copied out.
SpaceO(1)A few indices, besides the output.

Search directly for the left edge lo in [0, n - k]. For a candidate start mid, compare the element just left of the window, arr[mid], with the element just past it, arr[mid + k]. If x - arr[mid] > arr[mid + k] - x, the window starting at mid keeps a worse element than it drops, so the start must move right; otherwise it can stay at mid or move left.

  1. lo = 0, hi = n - k.
  2. While lo < hi: mid = (lo + hi) / 2; if x - arr[mid] > arr[mid + k] - x, lo = mid + 1; else hi = mid.
  3. Return arr[lo..lo + k - 1].
class Solution {
    public List<Integer> findClosestElements(int[] arr, int k, int x) {
        int lo = 0, hi = arr.length - k;
        while (lo < hi) {
            int mid = (lo + hi) >>> 1;
            if (x - arr[mid] > arr[mid + k] - x) lo = mid + 1;
            else hi = mid;
        }
        List<Integer> res = new ArrayList<>();
        for (int i = lo; i < lo + k; i++) res.add(arr[i]);
        return res;
    }
}

Edge cases to test

  • x smaller than every element or larger than every element
  • k equal to the array length
  • Ties in distance: the smaller value wins
  • Duplicates in the array

Hints

Hint 1

The answer is always a contiguous block of k elements of the sorted array.

Hint 2

Start with the whole array and drop the end whose element is farther from x.

Hint 3

Binary search for the left edge lo of the block: compare x - arr[mid] with arr[mid + k] - x.

FAQ

What is the best time complexity for Find K Closest Elements?

Optimal (binary search on the window start) runs in O(log(n - k) + k) time and O(1) extra space. Binary search over n - k + 1 starts, then k elements are copied out.

Which pattern does Find K Closest Elements use?

It is a binary search problem that uses the bisect pattern. Other problems with the same pattern: bisect_left, bisect_right, Search Insert Position, Floor in a Sorted Array.

Is there a brute force solution for Find K Closest Elements?

Yes. Brute force (sort by distance) takes O(n log n) time and O(n) space. Sort a copy of the values by distance to x, breaking ties by the smaller value, take the first k and sort those back into ascending order.

Which edge cases should I test for Find K Closest Elements?

x smaller than every element or larger than every element; k equal to the array length; Ties in distance: the smaller value wins; Duplicates in the array.