Skip to main content

658. Find K Closest Elements

mediumAsked at Elastic

Return the k integers in a sorted array closest to a target value. Elastic asks this because nearest-neighbor lookup in a sorted index is the core of Elasticsearch's range queries and numeric field approximations — binary search to anchor + window expansion is a real optimization pattern in search engines.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Source citations

Public interview reports confirming this problem appears in Elastic loops.

  • Glassdoor (2025-11)— Elastic SWE candidates report binary search and sorted-range problems appearing as a distinct category in mid-level onsite rounds.
  • Blind (2025-09)— Find K Closest Elements cited in Elastic prep threads as a problem that combines binary search with sliding-window thinking relevant to their numeric indexing domain.

Problem

Given a sorted integer array arr, two integers k and x, return the k closest integers to x in the array. The result should also be sorted in ascending order. An integer a is closer to x than an integer b if: |a - x| < |b - x|, or |a - x| == |b - x| and a < b.

Constraints

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

Examples

Example 1

Input
arr = [1,2,3,4,5], k = 4, x = 3
Output
[1,2,3,4]

Explanation: The 4 numbers closest to 3 are 1,2,3,4 (all within distance 2). 5 is farther (distance 2, but 1 is preferred by tiebreak).

Example 2

Input
arr = [1,2,3,4,5], k = 4, x = -1
Output
[1,2,3,4]

Explanation: All closest 4 elements are at the left end.

Approaches

1. Binary search on left boundary of window

Binary search for the left index of the k-element window. The window [left, left+k-1] is valid. Compare arr[mid] and arr[mid+k]: if x - arr[mid] > arr[mid+k] - x, the window should shift right.

Time
O(log(n-k))
Space
O(1) excluding output
function findClosestElements(arr, k, x) {
  let left = 0, right = arr.length - k;
  while (left < right) {
    const mid = Math.floor((left + right) / 2);
    // Compare distances of left and right ends of candidate window
    if (x - arr[mid] > arr[mid + k] - x) {
      left = mid + 1; // window too far left, shift right
    } else {
      right = mid;    // window good or too far right, keep or shift left
    }
  }
  return arr.slice(left, left + k);
}

Tradeoff: O(log(n-k)) — optimal. The binary search on the window's left index is the key insight. The comparison x - arr[mid] > arr[mid+k] - x avoids needing to expand from a midpoint.

2. Two-pointer expansion from insertion point

Binary search for x's insertion point. Expand left and right pointers outward, always choosing the closer element, until k elements are collected.

Time
O(log n + k)
Space
O(1) excluding output
function findClosestElements(arr, k, x) {
  // Find insertion point
  let lo = 0, hi = arr.length;
  while (lo < hi) {
    const mid = Math.floor((lo + hi) / 2);
    if (arr[mid] < x) lo = mid + 1; else hi = mid;
  }
  let left = lo - 1, right = lo;
  const result = [];
  while (result.length < k) {
    if (left < 0) { result.push(arr[right++]); }
    else if (right >= arr.length) { result.push(arr[left--]); }
    else if (x - arr[left] <= arr[right] - x) { result.push(arr[left--]); }
    else { result.push(arr[right++]); }
  }
  return result.sort((a, b) => a - b);
}

Tradeoff: O(log n + k) — slightly worse than the window approach for large k, but easier to reason about when asked to trace through an example.

Elastic-specific tips

Elastic interviewers appreciate the window-binary-search approach because it mirrors how Elasticsearch binary-searches BKD tree nodes to find close numeric values. Explain the comparison: 'I compare the distances of the two outermost elements of the candidate window — if the left end is farther from x than the right end, the entire window needs to shift right.' This demonstrates you understand why the window, not the midpoint, is the thing to search on.

Common mistakes

  • Searching for x's exact position rather than the window's left position — the correct binary search space is [0, n-k].
  • Using > instead of >= in the tiebreak comparison — the problem specifies the smaller element wins ties, so use > to keep left when equal.
  • Returning the slice as-is without sorting — the two-pointer approach may collect elements out of order.
  • Setting right = arr.length instead of arr.length - k in the window approach — the window must fit entirely within the array.

Follow-up questions

An interviewer at Elastic may pivot to one of these next:

  • Find Closest Value in BST — same idea but on a tree structure.
  • K Closest Points to Origin (LC 973) — generalize nearest-neighbor to 2D coordinates with a heap.
  • How does Elasticsearch's BKD tree accelerate range and nearest-neighbor queries on numeric fields?

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

FAQ

Why is the binary search space [0, arr.length - k] not [0, arr.length - 1]?

We are searching for the left boundary of a k-element window. The window must end at most at index arr.length - 1, so the left boundary can be at most arr.length - k.

Why compare arr[mid] and arr[mid+k] instead of distances from x?

We compare the left end (arr[mid]) and right end (arr[mid+k]) of the candidate window to decide which direction to shift. If the right end is closer to x, shift the window right by moving left = mid + 1.

Practice these live with InterviewChamp.AI

Drill Find K Closest Elements and other Elastic interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →