Problem Understanding
From the sorted integer array arr, pick the k values nearest to x.
If |a - x| == |b - x|, the smaller number is chosen. The result should be sorted in ascending order.
Example:
- Input:
arr = [1,2,3,4,5],k = 4,x = 3 - Output:
[1,2,3,4]
Algorithm Strategy
The heap baseline — O(n log k). Treat it like any top-k problem: push every value onto a max-heap keyed by (|value − x|, value) and pop whenever it holds more than k. It works on any array, sorted or not.
A sorted array does better — O(n). Distance from x only falls and then rises along a sorted array, so the k closest values are one contiguous run, and the farther end of any window is its farthest value. Start with the whole array as the window [L, R] and shrink it:
- While the window holds more than k values, compare its two ends.
- If
arr[L]is strictly farther fromxthanarr[R], dropL. - Otherwise drop
R— on a tie the smaller value,arr[L], is the one to keep. - Return
arr[L..R].
Binary search can find where the window starts in O(log(n − k)); the shrink is the simplest correct version, and it is what the code below does.
Interactive Visualization
The window [L, R] starts as the whole array, with each value's distance from x beneath it. Its two ends are compared and the farther one is dropped until k values remain.
Dry Run (Two Pointers)
Input: arr = [1, 2, 3, 4, 5], k = 4, x = 3
| Step | L | R | abs(arr[L] − x) | abs(arr[R] − x) | Action |
|---|---|---|---|---|---|
| 1 | 0 | 4 | 2 | 2 | A tie: keep the smaller 1, drop 5 (R = 3) |
| 2 | 0 | 3 | - | - | 4 values = k: stop |
Result: [1, 2, 3, 4]
Input: arr = [1, 2, 3, 4, 5, 6, 7], k = 3, x = 5
| Step | L | R | abs(arr[L] − x) | abs(arr[R] − x) | Action |
|---|---|---|---|---|---|
| 1 | 0 | 6 | 4 | 2 | Drop 1 (L = 1) |
| 2 | 1 | 6 | 3 | 2 | Drop 2 (L = 2) |
| 3 | 2 | 6 | 2 | 2 | A tie: drop 7 (R = 5) |
| 4 | 2 | 5 | 2 | 1 | Drop 3 (L = 3) |
| 5 | 3 | 5 | - | - | 3 values = k: stop |
Result: [4, 5, 6]
Edge Cases
- x left of every value: the right end is always farther, so the answer is the first k values.
- x right of every value: the answer is the last k values.
- k = n: the loop never runs and the whole array is returned.
- Ties: drop
R. The comparison that dropsLmust be a strict>, or a tie would throw away the smaller value. - Duplicates: equal values have equal distances, and the same tie rule applies.
Solution
The shrinking window, O(n) time and O(1) extra space — the same method in every language.
Find K Closest Elements Code
1/**2 * @param {number[]} arr3 * @param {number} k4 * @param {number} x5 * @return {number[]}6 */7var findClosestElements = function(arr, k, x) {8 let L = 0;9 let R = arr.length - 1;1011 while (R - L + 1 > k) {12 if (Math.abs(arr[L] - x) > Math.abs(arr[R] - x)) {13 L++;14 } else {15 R--;16 }17 }1819 return arr.slice(L, R + 1);20};