Find K Closest Elements
The briefingthe full drill, in my own words
The drill: From a sorted array, pick the k values nearest to a target x — ties go to the smaller value — handed back in ascending order. Sortedness means the winners always sit shoulder-to-shoulder: one contiguous window, and the only unknown is where its left edge falls.
A sorted array of integers arrives along with a count k and a target value x. The task is to identify the k array values that sit closest to x and hand them back as a list of exactly k numbers.
Closeness is measured by absolute distance to x. When two values are equally close, the smaller one is preferred over the larger one — that's the only tiebreak rule in play.
The result must be sorted in ascending order, and it always draws from the original array's values rather than their positions. k never exceeds the array's own length.
- array holds a handful up to several thousand sorted integers
- k is between 1 and the array's length
- ties in distance favor the smaller of the two values
- answer comes back as k values in ascending order
The hintstake only what you need
HINT 1 THE NUDGE
Ranking every element by distance to x works, but it throws away the gift in the problem: the array is already sorted. In sorted order, where must the k winners sit relative to each other?
HINT 2 THE STRUCTURE
They form one contiguous block of length k. Choosing k elements collapses into choosing one number — the left edge, an index between 0 and n − k.
HINT 3 ONE STEP FROM THE ANSWER
Binary-search that left edge. At candidate mid, compare x − arr[mid] with arr[mid + k] − x: strictly larger means the window belongs further right; otherwise it starts at or before mid. Strict inequality is what sends ties to the smaller values.
Coach's boardthe pattern, step by step
Sorted array, k=3, x=7. The answer is one contiguous window of width 3 — binary search its left edge between 0 and 2.
The splitstwo paces, two languages
class Solution:
def findClosestElements(self, arr: List[int], k: int, x: int) -> List[int]:
lo, hi = 0, len(arr) - k # candidate left edges for the k-window
while lo < hi:
mid = (lo + hi) // 2
# strict >: on an exact tie the window stays left, keeping smaller values
if x - arr[mid] > arr[mid + k] - x:
lo = mid + 1
else:
hi = mid
return arr[lo:lo + k]class Solution:
def findClosestElements(self, arr: List[int], k: int, x: int) -> List[int]:
# rank by distance to x, value breaking ties; then restore ascending order
ranked = sorted(arr, key=lambda a: (abs(a - x), a))
return sorted(ranked[:k])class Solution {
public List<Integer> findClosestElements(int[] arr, int k, int x) {
int lo = 0, hi = arr.length - k; // candidate left edges for the k-window
while (lo < hi) {
int mid = (lo + hi) / 2;
// strict >: on an exact tie the window stays left, keeping smaller values
if (x - arr[mid] > arr[mid + k] - x) {
lo = mid + 1;
} else {
hi = mid;
}
}
List<Integer> out = new ArrayList<>();
for (int i = lo; i < lo + k; i++) out.add(arr[i]);
return out;
}
}class Solution {
public List<Integer> findClosestElements(int[] arr, int k, int x) {
Integer[] ranked = new Integer[arr.length];
for (int i = 0; i < arr.length; i++) ranked[i] = arr[i];
// rank by distance to x, value breaking ties; then restore ascending order
Arrays.sort(ranked, (a, b) -> {
int da = Math.abs(a - x), db = Math.abs(b - x);
return da != db ? da - db : a - b;
});
List<Integer> out = new ArrayList<>();
for (int i = 0; i < k; i++) out.add(ranked[i]);
Collections.sort(out);
return out;
}
}✓ CHIP-TIMEDALL 4 SOLUTIONS RAN GREEN AGAINST SELF-AUTHORED CASES IN CI · JDK 21 · CPYTHON 3.12 · NOTHING PUBLISHES RED