Show problems as
Classic problem #658MediumArrayTwo PointersBinary SearchSliding WindowSortingHeap (Priority Queue)

Find K Closest Elements

Real-world version: Nearest Gauge Marks
Tracked in this browser only
Read Find K Closest Elements on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

A calibration bench carries gauge marks etched along a rail. Their readings are listed in arr from lowest to highest, and the same reading may be etched more than once. A technician aims the probe at reading x and wants the k marks nearest to that aim.

Mark a is nearer than mark b when |a - x| is smaller than |b - x|, and when the two distances are equal the smaller reading is treated as the nearer one.

Return the k chosen readings listed from lowest to highest. When a reading is etched several times, each etching counts as its own mark.

Examples

Example 1

Input
arr = [2,5,9,13,20], k = 3, x = 10
Output
[5,9,13]

The distances from 10 are 8, 5, 1, 3 and 10. The three smallest belong to 9, 13 and 5, and the answer lists those readings from lowest to highest.

Example 2

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

Both 3 and 5 sit one away from 4. The tie goes to the smaller reading, so 3 is returned.

Example 3

Input
arr = [-9,-3,0,4], k = 3, x = -2
Output
[-3,0,4]

The distances are 7, 1, 2 and 6, so -3, 0 and 4 are the three nearest and -9 is left out.

Constraints

  • 1 <= k <= arr.length
  • 1 <= arr.length <= 10^4
  • arr is listed from lowest to highest.
  • -10^4 <= arr[i] <= 10^4
  • -10^4 <= x <= 10^4

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def find_closest_elements(arr: list[int], k: int, x: int) -> list[int]:
Java
public List<Integer> findClosestElements(int[] arr, int k, int x)

More on the same topics