Find K Closest Elements
Given a sorted array, find the k closest integers to x. The result should also be sorted in ascending order.

30:00

Find K Closest Elements
medium
Topics
Companies

Given a sorted array, find the k closest integers to x. The result should also be sorted in ascending order.

Example 1:
Input: {"arr":[1,2,3,4,5],"k":4,"x":3}
Output: [1,2,3,4]
Constraints:

  • 1≤k≤arr.length1 \leq k \leq \text{arr.length}

  • 1≤arr.length≤1041 \leq \text{arr.length} \leq 10^4

  • arr is sorted in ascending order.

  • −104≤arr[i],x≤104-10^4 \leq \text{arr}[i], x \leq 10^4

Input
arr ={"arr":[1,2,3,4,5],"k":4,"x":3}

Find 4 closest elements to 3. Binary search for window start in [0, 1]

Target:
x = 3
Find:
k = 4 closest
Sorted Array

1

2

3

4

5

0 L
1 R
2
3
4
Search Range:
[0, 1]
Algorithm Insight:

Binary search for the left boundary of the k-element window. Compare distance from x to arr[mid] vs arr[mid+k] to decide which direction to search.

Variables
No variables to display
DepthFunction Call
Stack empty
0/4