Find K Closest Elements
Medium · Arrays & Hashing · Array · Two Pointers · Binary Search · Sliding Window · Sorting · Heap (Priority Queue)
Problem
You are given a sorted integer array arr, and two integers k and x. Return the k elements of arr closest to x, sorted in ascending order.
Value a counts as closer to x than b if |a - x| < |b - x|, or if |a - x| == |b - x| and a < b. So ties go to the smaller value.
Examples
Input: arr = [1,3,6,8,10], k = 3, x = 7 Output: [6,8,10]
Distances to 7 are 6, 4, 1, 1, 3, so 6, 8 and 10 are closest.
Input: arr = [2,4,6], k = 1, x = 5 Output: [4]
4 and 6 are both 1 away; the tie goes to the smaller value.
Input: arr = [-5,-1,0,20], k = 2, x = -30 Output: [-5,-1]
x lies left of the array, so the two leftmost elements win.
Constraints
- 1 <= k <= len(arr) <= 10^4
- arr is sorted in ascending order
- -10^4 <= arr[i], x <= 10^4
Approaches
- Shrink from both ends — time O(n − k), space O(1) beyond the output
Follow-up
If the array were not sorted, the answer would no longer be a window. Keep a max-heap of size k keyed by (|a − x|, a) for O(n log k), then sort the k survivors.
Related problems
Start free on Cariara · Coding problems · System design studio
