Generated by Codex with GPT-5

Quick facts

• Difficulty: MEDIUM
• Problem: Find K Closest Elements
• Topics: Array, Two Pointers, Binary Search, Sliding Window, Sorting, Heap (Priority Queue)

What the problem is asking

The input is already sorted. Given a target value x, the task is to return the k values that are closest to it, still in sorted order.

Closeness has one important tie rule: if two values are equally far from x, the smaller value wins. That tie rule should influence the algorithm instead of being cleaned up afterward.

The optimal idea

The answer is a contiguous window of length k in the sorted array. If a chosen value sits on one side of an unchosen value that lies closer to x, swapping them would improve the answer. After the best k values are chosen, there cannot be a skipped value trapped between them.

That turns the problem into a search over window starts. A window starting at index start covers:

• left edge: arr[start]
• right edge: arr[start + k - 1]

To decide whether the best window starts after a midpoint mid, compare the value that would fall off the left side, arr[mid], with the next value that could enter from the right, arr[mid + k].

If arr[mid] is farther from x than arr[mid + k], the current window is too far left, so every valid answer at or before mid can be discarded. Otherwise, the left value is at least as good. That includes ties, where the smaller left value must stay preferred, so the search keeps mid in play.

Binary search on that decision finds the best start index in O(log(n - k)) comparisons. Slicing the k values for the answer costs O(k).

How to derive it in an interview

A direct first idea is to expand two pointers around the insertion point for x. That works in O(log n + k) time after a binary search for the insertion point, but the pointer logic has several edge cases when one side runs out.

The window view is cleaner. The input order is already sorted, and the output must stay sorted, so look for a sorted block rather than picking values one at a time. There are only n - k + 1 possible length-k blocks. Moving one block right drops one left endpoint and adds one right endpoint, so those are the only two values that matter for the move decision.

That move decision is monotonic. Once the right contender is better than the left endpoint, windows that start even farther left cannot be optimal. That monotonicity is exactly what binary search needs.

Python solution

from collections.abc import Sequence


def find_best_window_start(
    sorted_values: Sequence[int],
    count: int,
    target: int,
) -> int:
    """Return the start index of the closest contiguous window."""
    left_start = 0
    right_start = len(sorted_values) - count

    while left_start < right_start:
        middle_start = (left_start + right_start) // 2

        # Compare the left value that would be dropped with the next value
        # that could enter if the window moves one step to the right.
        left_distance = target - sorted_values[middle_start]
        right_distance = sorted_values[middle_start + count] - target

        if left_distance > right_distance:
            left_start = middle_start + 1
        else:
            # Equal distances keep the smaller, left-side value.
            right_start = middle_start

    return left_start


def k_closest_elements(
    sorted_values: Sequence[int],
    count: int,
    target: int,
) -> list[int]:
    """Return the closest count values in ascending order."""
    if count < 0:
        raise ValueError("count must be non-negative")
    if count > len(sorted_values):
        raise ValueError("count cannot exceed the input length")
    if count == 0:
        return []

    window_start = find_best_window_start(sorted_values, count, target)
    return list(sorted_values[window_start:window_start + count])


class Solution:
    def findClosestElements(
        self,
        arr: list[int],
        k: int,
        x: int,
    ) -> list[int]:
        """LeetCode entry point."""
        return k_closest_elements(arr, k, x)

Why this works

Every valid answer can be represented as a length-k window. Consider the window that starts at mid. If arr[mid] is farther from x than arr[mid + k], replacing the left endpoint with that right contender produces a better window, so the best answer cannot start at mid or earlier.

Otherwise, the left endpoint is no worse than the right contender. The current start or an earlier one may still be optimal. When the distances tie, keeping the left side also enforces the rule that smaller values win.

The search range always retains at least one optimal start index and shrinks until it contains one index. The final slice returns exactly that closest contiguous window, already sorted because it comes from the sorted input.

The time complexity is O(log(n - k) + k): binary search locates the window start, and producing the answer writes k values. The extra space complexity is O(k) for the returned list and O(1) beyond the output.

Interview follow-ups

How would this change if the array were not sorted?

Without sorted order, the contiguous-window property disappears. One practical approach is to select by the key (abs(value - x), value), keep the best k values with a heap or a selection algorithm, then sort the chosen values before returning them.

A heap of size k is straightforward when the array is large or streaming: keep only the current best candidates and evict the worst one as new values arrive. That takes O(n log k) time plus O(k log k) to sort the final answer. Sorting the whole array by closeness is simpler to describe, but it spends O(n log n) time even though only k values are needed.

Can this be solved with two pointers?

Yes. First locate where x would be inserted with binary search. Then place one pointer on the element immediately left of that position and one pointer on the element at or to the right. Repeatedly choose the closer side until k values are covered, preferring the left side on ties.

That method takes O(log n + k) time and can be useful when the interviewer wants the answer built from the target outward. The tradeoff is more boundary handling: either pointer may run off the array before the other does. The fixed-window binary search keeps the result contiguous throughout and returns a simple slice.

What if the interviewer asks for the closest values to many targets?

The sorted array can be reused as-is. For each target, the same binary search over start indices finds the best length-k window without rebuilding any data structure. Each query costs O(log(n - k) + k) because the output itself still contains k values.

If k is small and query volume is high, that bound is already close to optimal for returning materialized lists. If the API can return window boundaries or iterators instead of copying the values each time, the search part stays logarithmic and the copy cost can be deferred.

What if ties should prefer larger values instead?

The binary-search comparison changes at the equality case. In this problem, equal distances preserve the left-side candidate because it is smaller. If larger values should win, equal distances should move the window right instead.

That means the branch should advance left_start when the left and right distances are equal. The asymptotic complexity does not change, but the equality rule must be stated clearly because it determines which of two equally close windows is valid.

Why not use a heap for the sorted version too?

A heap works, but it ignores the strongest structure in the input. For a sorted array, the best k values are contiguous and the search space is just the possible window starts. Binary search can find that window before the answer is copied.

The heap version usually costs O(n log k) time and O(k) working space. The window search avoids scanning all n values when k is much smaller than n, and it naturally returns the answer in sorted order.

Practical takeaway

Find K Closest Elements becomes simpler once the answer is viewed as a window. Sorted input turns “choose the best k values” into “find the one best window start,” and the tie rule tells the binary search which side to keep when both windows are equally close.