Find K Closest Elements

MEDIUM✓ CHIP-TIMEDLC #658 — FULL STATEMENT ↗

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.

THE BRIEFING — THE FULL DRILL, IN MY OWN WORDS

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.

EX 01

arr = [2, 5, 6, 9, 11] · k = 3 · x = 7

→ [5, 6, 9]

WINDOW LANDS MID-ARRAY

EX 02

arr = [10, 20, 30, 40] · k = 2 · x = 3

→ [10, 20]

X BELOW EVERYTHING — WINDOW PINS LEFT

EX 03

arr = [1, 3, 5, 7] · k = 3 · x = 50

→ [3, 5, 7]

X ABOVE EVERYTHING — WINDOW PINS RIGHT

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 HINTS — TAKE 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 BOARD — THE PATTERN, STEP BY STEP

BINARY SEARCH THE WINDOW EDGEPATTERN · BINARY SEARCH ON THE ANSWERarr = [2, 5, 6, 9, 11] · k = 3 · x = 7

COMPARE — x−arr[mid] vs arr[mid+k]−x

— empty —

STEP 1

Sorted array, k=3, x=7. The answer is one contiguous window of width 3 — binary search its left edge between 0 and 2.

STEP 1 / 5 · ← → WORK TOO

THE SPLITS — TWO PACES, TWO LANGUAGES

grind/find-k-closest-elements.py — RACE PACE

LANG ▸

PACE ▸

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]

TIME O(LOG(N−K) + K)SPACE O(1)PYTHON · RACE PACE · 11 LN

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])

TIME O(N LOG N)SPACE O(N)PYTHON · TRAINING PACE · 5 LN

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;
    }
}

TIME O(LOG(N−K) + K)SPACE O(1)JAVA · RACE PACE · 17 LN

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;
    }
}

TIME O(N LOG N)SPACE O(N)JAVA · TRAINING PACE · 15 LN

✓ CHIP-TIMED — ALL 4 SOLUTIONS RAN GREEN AGAINST SELF-AUTHORED CASES IN CI · JDK 21 · CPYTHON 3.12 · NOTHING PUBLISHES RED