#658 Find K Closest Elements
the problem
In plain words
Given a sorted array arr, an integer k and a value x, return the k values of arr that are closest to x, in ascending order. Value a is closer than b if |a − x| < |b − x|; if the distances tie, the smaller value wins.
in arr = [1,2,3,4,5], k = 4, x = 3
out [1,2,3,4]
1 and 5 are both 2 away from 3; the smaller one, 1, wins the tie.
in arr = [1,1,2,3,4,5], k = 4, x = -1
out [1,1,2,3]
x is left of everything, so the first four values are closest.
- 1 ≤ k ≤ arr.length ≤ 10⁴
- arr is sorted in ascending order
- −10⁴ ≤ arr[i], x ≤ 10⁴
your turn
Try it before you peek
Read the examples, say the brute force out loud, then write code: here or on LeetCode ↗. Stuck for 20 minutes? Open one hint at a time.
Solve it in the browser
LeetCode-style: complete the class. Compiled by the real javac (Java 17) and judged right here — nothing is sent anywhere.
Solutions are hidden so you can try first. Even 20 minutes of real effort makes the answer stick far better than reading it.
Marking the problem solved, or opening every hint, also shows it.
the aha
Key insight
patternModified binary searchTwo pointers (opposite ends)
The answer is always k neighbours in a row — a window of the sorted array. So only its start is unknown, somewhere in [0, n − k]. For a start mid, compare the value just inside on the left, arr[mid], with the value just outside on the right, arr[mid + k]: the farther one tells you which way the window must move.
solutions
From brute force to optimal
Sort all values by (distance to x, value), take the first k, sort them back into ascending order.
- Box the values into a List<Integer>.
- Sort with a comparator: |a − x|, then a.
- Take k, sort ascending.
The sort dominates; it ignores that arr is already sorted.
The boxed copy.
class Solution { public List<Integer> findClosestElements(int[] arr, int k, int x) { List<Integer> all = new ArrayList<>(); for (int a : arr) all.add(a); all.sort(Comparator.comparingInt((Integer a) -> Math.abs(a - x)) // closer first, .thenComparingInt(a -> a)); // ties: the smaller value List<Integer> result = new ArrayList<>(all.subList(0, k)); Collections.sort(result); // the answer must be ascending return result; }}Start with the whole array and drop whichever end is farther from x until only k values are left.
- lo = 0, hi = n − 1.
- While the window is wider than k: x − arr[lo] > arr[hi] − x → lo++, else hi−− (a tie drops the bigger value).
- Return arr[lo..hi].
One end moves per step until n − k values are dropped (plus O(k) to copy the answer).
Two indices besides the output list.
class Solution { public List<Integer> findClosestElements(int[] arr, int k, int x) { int lo = 0, hi = arr.length - 1; while (hi - lo + 1 > k) { // too wide: drop the end that is farther from x if (x - arr[lo] > arr[hi] - x) lo++; // left end is strictly farther else hi--; // right end is farther, or a tie (keep the smaller) } List<Integer> result = new ArrayList<>(k); for (int i = lo; i <= hi; i++) result.add(arr[i]); return result; }}Search start positions [0, n − k]. If arr[mid + k] is closer to x than arr[mid], the window must start after mid; otherwise it starts at mid or earlier.
- lo = 0, hi = n − k.
- While lo < hi: mid = lo + (hi − lo) / 2.
- x − arr[mid] > arr[mid + k] − x → lo = mid + 1; else hi = mid.
- Return arr[lo .. lo + k − 1].
A binary search over n − k + 1 starts, then k values copied.
Only indices besides the output list.
class Solution { public List<Integer> findClosestElements(int[] arr, int k, int x) { int lo = 0, hi = arr.length - k; // the window [start, start + k) starts in [0, n - k] while (lo < hi) { int mid = lo + (hi - lo) / 2; // try the window that starts at mid if (x - arr[mid] > arr[mid + k] - x) { // arr[mid + k] is closer than arr[mid] lo = mid + 1; // so the window must start after mid } else { hi = mid; // arr[mid] is at least as close: start at mid or earlier } } List<Integer> result = new ArrayList<>(k); for (int i = lo; i < lo + k; i++) result.add(arr[i]); return result; }}Dry run
in the room
How to say it in the interview
talk track
- Say why the answer is contiguous: if you skipped a value inside the window, it would be closer than one you kept.
- Offer the two-pointer shrink first — O(n − k) and easy to prove.
- Then binary search the start, and explain the comparison x − arr[mid] vs arr[mid + k] − x, including how ties keep the left side.
traps
- Using
Math.absin the window comparison: with duplicates like [1,1,2,2,2,2,2,3,3], k = 3, x = 3 it returns [2,2,2] instead of [2,3,3]. - Searching starts in [0, n − 1] instead of [0, n − k] — arr[mid + k] then runs off the end.
- Forgetting the tie rule: on equal distances keep the smaller value, which is the left side.
what they ask next
Follow-ups
What if the array is not sorted?
Use a max-heap of size k ordered by (distance, value): O(n log k). Then sort the k values you kept.
Is there an O(log n + k) version that starts from x itself?
Yes: lower bound finds where x would go, then two pointers expand outwards k times, each step taking the closer side.
before you submit
Edge cases to test
- x outside the array: the answer is the first k or the last k values.
- Ties go to the smaller value: [1, 3], k = 1, x = 2 → [1].
- Duplicates: [1,1,2,2,2,2,2,3,3], k = 3, x = 3 → [2,3,3].
- k = n: the whole array.
practise next
Similar problems
- #973K Closest Points to OriginMediumin Heaps
- #35Search Insert PositionEasyin Binary Search
- #167Two Sum II - Input Array Is SortedMediumin Two Pointers