Code Logo

Find K Closest Elements

Published at24 Jul 2026
Created by
Medium 5 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

Solution Approach

Find k closest elements to a target value x in a sorted array. Use binary search to find the insertion point of x, then expand a window outward using two pointers. Start with left and right pointers around the insertion point. Expand toward the side with the closer value until the window contains k elements.

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

Binary search finds the start index of the k-element window. The comparison x - arr[mid] vs arr[mid+k] - x checks which side is farther from x, narrowing to the closer side.

Time complexity is O(log n + k), space complexity is O(k).

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);
    }
}