Code Logo

Find K Closest Elements

Published at24 Jul 2026
Created by
Medium 0 views
Like0

Given a sorted integer array arr, an integer k, and an integer x, return the k closest integers to x in the array. The result should be sorted in ascending order. Closeness is measured by absolute difference |arr[i] - x|. If there is a tie, the smaller element is preferred.

A naive approach would sort by absolute difference and take the first k elements, requiring O(n log n) time. Binary search achieves O(log n + k) by first finding the optimal window start position. The window of size k is always contiguous — the k closest elements form a contiguous subarray in the sorted array.

The binary search checks candidate start positions. For a given mid, compare arr[mid] and arr[mid + k]: if x is closer to arr[mid] than to arr[mid + k], the window start should be earlier; otherwise, later. This works because the window start must be between index 0 and n - k, and the comparison tells us which side to search.

Edge cases include x smaller than all elements (return first k), x larger than all elements (return last k), k equal to array length (return the whole array), and ties where arr[mid] and arr[mid + k] are equally close to x.

The binary search comparison uses the property that the k closest elements form a contiguous window. By comparing arr[mid] against arr[mid+k] relative to x, we determine whether to shift the window left or right. This avoids having to sort by absolute difference, keeping the algorithm efficient.

Example Input & Output

Example 1
Input
[1,1,2,3,4,5], 2, 1
Output
[1,1]
Explanation

Two 1s are closest.

Example 2
Input
[1,2,3,4,5], 4, 3
Output
[1,2,3,4]
Explanation

Four closest to 3 are [1,2,3,4].

Example 3
Input
[1,2,3,4,5], 3, 3
Output
[2,3,4]
Explanation

Three closest to 3 are [2,3,4].

Example 4
Input
[1], 1, 1
Output
[1]
Explanation

Single element.

Example 5
Input
[1,2,3,4,5], 4, -1
Output
[1,2,3,4]
Explanation

x < all, pick first k.

Algorithm Flow

Recommendation Algorithm Flow for Find K Closest Elements
Recommendation Algorithm Flow for Find K Closest Elements

Solution Approach

Binary search window start between 0 and n-k. Compare arr[mid] with arr[mid+k] relative to x. Return the k-length subarray.

function solution(arr, k, x) {
  var lo = 0, hi = arr.length - k;
  while (lo < hi) {
    var mid = Math.floor((lo + hi) / 2);
    if (x - arr[mid] > arr[mid + k] - x) lo = mid + 1;
    else hi = mid;
  }
  return arr.slice(lo, lo + k);
}

Time O(log n + k), Space O(1).

Best Answers

java
import java.util.*;
class Solution {
    public int[] solution(int[] arr, int k, int x) {
        int lo = 0, hi = arr.length - k;
        while (lo < hi) {
            int mid = lo + (hi - lo) / 2;
            if (x - arr[mid] > arr[mid + k] - x) lo = mid + 1;
            else hi = mid;
        }
        return Arrays.copyOfRange(arr, lo, lo + k);
    }
}