Find K Closest Elements

Shrink both ends

The answer is one sorted window. Start with the whole array and discard one endpoint at a time until exactly k values remain.

If the endpoints are equally far from x, discard the right one: it's larger, while the tie rule favors the smaller value.

def find_closest_elements(arr: list[int], k: int, x: int) -> list[int]:
    left, right = 0, len(arr) - 1
    while right - left + 1 > k:
        left_distance = abs(arr[left] - x)
        right_distance = abs(arr[right] - x)
        if left_distance <= right_distance:
            right -= 1
        else:
            left += 1
    return arr[left:right + 1]

Sorted order makes this safe. If the left endpoint loses to the right endpoint, it also loses to every value between them on the route toward x; the symmetric argument handles the right endpoint.

Time O(n), space O(k) for the returned slice, with O(1) auxiliary space.

Binary-search the window

There are n - k + 1 possible size-k windows. Search their left-edge indices from 0 through n - k.

At candidate mid, only two values decide whether the best window lies farther right:

• arr[mid], the value you would drop by shifting right, and
• arr[mid + k], the value you would gain.

If the left value is farther from x, shift right. Otherwise keep this window or search left; equality stays left to honor the smaller-value tie rule.

def find_closest_elements(arr: list[int], k: int, x: int) -> list[int]:
    left, right = 0, len(arr) - k
    while left < right:
        mid = (left + right) // 2
        if x - arr[mid] > arr[mid + k] - x:
            left = mid + 1
        else:
            right = mid
    return arr[left:left + k]

The comparison also works when x sits outside the array: one side becomes negative, which drives the search toward the nearest end.

Time O(log(n − k) + k), space O(k) for the returned slice, with O(1) auxiliary space.