Find K Closest Elements

You are given an array arr sorted in non-decreasing order, a count k and a target value x. Pick the k elements of arr that are closest to x and return them sorted in ascending order.

Closeness is measured by absolute difference: a is closer than b when |a - x| < |b - x|. When two elements are equally close, the smaller one is preferred. x itself does not have to appear in the array.

Example 1

Example 2

Example 3

Constraints

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

Pattern Path · Binary Search · problem 61 of 169

Start simple

Sort all elements by (distance to x, value), take the first k and sort them again: O(n log n) time.

The key idea

In a sorted array, if some element is chosen then every element between it and x is at least as close, so the k closest elements form one contiguous window arr[lo .. lo + k - 1]. We only need to find lo.

Consider a candidate start mid and compare the element we would drop, arr[mid], with the element just past the window, arr[mid + k]. If x - arr[mid] > arr[mid + k] - x, the right-hand element is strictly closer, so this window and every window starting further left is beaten by sliding right: set lo = mid + 1. Otherwise the left end is at least as good (ties favour the smaller value), so the best start is mid or earlier: set hi = mid.

Using the signed differences rather than absolute values matters: it keeps the comparison correct even when x lies outside the window or when arr[mid] == arr[mid + k]. The search runs over n - k + 1 starts and then slices k elements.

Complexity

• Time: O(log(n - k) + k)
• Space: O(1) extra (O(k) for the output)

Python

class Solution:
    def findClosestElements(self, arr, k, x):
        # Binary search for the start of the best window of length k.
        lo, hi = 0, len(arr) - k
        while lo < hi:
            mid = (lo + hi) // 2
            # arr[mid + k] is strictly closer than arr[mid]: shift right.
            if x - arr[mid] > arr[mid + k] - x:
                lo = mid + 1
            else:
                hi = mid
        return arr[lo:lo + k]

JavaScript

var findClosestElements = function(arr, k, x) {
  // Binary search for the start of the best window of length k.
  let lo = 0, hi = arr.length - k;
  while (lo < hi) {
    const mid = (lo + hi) >> 1;
    // arr[mid + k] is strictly closer than arr[mid]: shift right.
    if (x - arr[mid] > arr[mid + k] - x) lo = mid + 1;
    else hi = mid;
  }
  return arr.slice(lo, lo + k);
};

What the interviewer is checking

It tests whether you can binary search on the answer's position rather than on a value, and whether your comparison handles ties and duplicates exactly.

Mistakes to avoid

• Comparing absolute distances |arr[mid] - x| and |arr[mid + k] - x|, which breaks when both ends are equal values on the same side of x.
• Letting hi start at n - 1 instead of n - k, so arr[mid + k] reads past the end.
• Breaking ties towards the larger value; the smaller one must win.
• Forgetting that x may lie below or above every element.

Follow-ups to expect

• Solve it with two pointers shrinking from both ends. (Drop the farther end, O(n - k).)
• What if the input were unsorted? (Max-heap of size k by distance.)
• What if queries arrive repeatedly for different x? (Binary search per query.)

In real software

Nearest-neighbour lookups on a sorted key, such as the k readings closest to a timestamp in a time-series store or the k prices nearest a quote in an order book.

Practice next