K Closest Elements to X

Problem Statement

Given an array of integers arr, an integer k, and a target value x, return the k values in arr that are closest to x by absolute difference. Results may be returned in any order (unless the problem asks for sorted).

Input

An integer array arr, target value x, and the count k.

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

Output

The k closest values.

[1, 2, 3, 4]
 
// distances from 3:
// 1→2  2→1  3→0  4→1  5→2
// smallest 4 distances: 0, 1, 1, 2 → values 3, 2, 4, 1

Constraints

• 1 ≤ k ≤ arr.length ≤ 10⁴
• -10⁴ ≤ arr[i], x ≤ 10⁴

Intuition

“Closest to X” is just “smallest by |x − value|”. We want the K smallest distances — classic max-heap-of-size-K. Push (distance, value) tuples and keep the heap capped at K; whatever remains is our answer.

num  dist  heap after push           heap after evict (size > 4)
 1    2    [(2,1)]                   —
 2    1    [(2,1),(1,2)]             —
 3    0    [(2,1),(1,2),(0,3)]       —
 4    1    [(2,1),(1,2),(0,3),(1,4)] —
 5    2    push → (2,1) & (2,5) tie  pop max → {(1,2),(0,3),(1,4),(2,?)}
 
result values (sorted): [1, 2, 3, 4] ✓

Solution

import heapq
 
def findClosestElements(arr: list[int], k: int, x: int) -> list[int]:
    max_heap: list[tuple[int, int]] = []    # (-distance, value)
    for num in arr:
        dist = abs(num - x)
        heapq.heappush(max_heap, (-dist, num))
        if len(max_heap) > k:
            heapq.heappop(max_heap)         # evict the farthest
    return sorted(v for _, v in max_heap)

function findClosestElements(arr: number[], k: number, x: number): number[] {
  // max-heap by distance — larger distance has higher priority to be evicted
  const h = new Heap<[number, number]>((a, b) => b[0] - a[0]);
  for (const num of arr) {
    const dist = Math.abs(num - x);
    h.push([dist, num]);
    if (h.size > k) h.pop();
  }
  const out: number[] = [];
  while (h.size > 0) out.push(h.pop()![1]);
  return out.sort((a, b) => a - b);
}

Complexity

Edge Case Thinking