Find K Closest Elements — Solution

Problem

Given a sorted integer array and two integers k and x, return the k integers from the array that are closest to x, in sorted order. When two integers are equidistant from x, the smaller one is preferred.

• Input: arr = [1, 2, 3, 4, 5], k = 4, x = 3
• Output: [1, 2, 3, 4]
• Explanation: Elements 1 and 5 are both distance 2 from x=3, so 1 is preferred, making [1,2,3,4] the optimal window.

Counter-example: arr = [1, 2, 3, 4, 5], k = 4, x = 5 → [2, 3, 4, 5]. The four rightmost elements are chosen because 1 is farther from x=5 than any of 2–5.

Intuition

Because the array is sorted, the k closest elements always form a contiguous window — there is never a reason to skip over an element to grab a farther one. The problem reduces to finding where that window starts. Both approaches below exploit this contiguity: one shrinks from the outside, the other binary searches for the left boundary directly.

Approach 1 — Two Pointers

Start with the full array and repeatedly remove the endpoint that is farther from x until exactly k elements remain. On a tie, remove from the right so the smaller (left) element is kept.

1. Initialize left = 0, right = len(arr) - 1.
2. While the window contains more than k elements:
3. If arr[left] is farther from x than arr[right], increment left.
4. Otherwise, decrement right — this handles ties by discarding the larger endpoint.
5. Return arr[left : right + 1].

1class Solution:
2    def findClosestElements(self, arr: List[int], k: int, x: int) -> List[int]:
3        left, right = 0, len(arr) - 1
4        while right - left + 1 > k:
5            # Discard the farther endpoint; tie goes to right so the smaller left element survives
6            if abs(arr[left] - x) > abs(arr[right] - x):
7                left += 1
8            else:
9                right -= 1
10        return arr[left:right + 1]

Time: O(n − k) — exactly n − k removals are performed, one per iteration.
Space: O(1) — only two index variables; the output slice is not counted.

Approach 2 — Binary Search on Window Start

Binary search directly for the optimal left boundary of the k-element window. At each midpoint, compare the signed distance from x to the window's left endpoint against the distance to the element just past the window's right endpoint — no abs() needed.

1. Set left = 0, right = len(arr) - k — these are the only valid starting indices for a k-element window.
2. While left < right, compute mid = (left + right) // 2.
3. If x - arr[mid] > arr[mid + k] - x, the right neighbor is closer to x, so shift the window right: left = mid + 1.
4. Otherwise, arr[mid] is at least as good a start as anything to its right: right = mid.
5. Return arr[left : left + k].

1class Solution:
2    def findClosestElements(self, arr: List[int], k: int, x: int) -> List[int]:
3        left, right = 0, len(arr) - k
4        while left < right:
5            mid = (left + right) // 2
6            # Signed comparison: no abs() needed — naturally handles x outside the array
7            # and breaks ties in favor of the smaller (leftmost) element
8            if x - arr[mid] > arr[mid + k] - x:
9                left = mid + 1  # right endpoint is closer; slide window right
10            else:
11                right = mid     # mid is still a valid candidate; narrow from the right
12        return arr[left:left + k]

Time: O(log(n − k) + k) — binary search over n − k positions, then O(k) to build the result slice.
Space: O(1) — only two index variables; the output does not count.

Complexity Summary

Common Mistakes

• Binary searching over [0, n-1] instead of [0, n-k] — the window accesses arr[mid + k], which goes out of bounds once the start index exceeds n - k.
• Flipping the comparison direction — writing arr[mid + k] - x > x - arr[mid] shifts the window the wrong way; trace arr = [1,3], k = 1, x = 2 to confirm your condition moves toward the correct answer.
• Adding abs() to the binary search condition — the signed expression x - arr[mid] > arr[mid + k] - x already handles x outside the array range and correctly breaks ties by favoring the leftmost (smaller) element; wrapping in abs() breaks that tie-breaking guarantee.
• Off-by-one in the result slice — after binary search converges, return arr[left : left + k], not arr[left : right + 1]; using left + k is unambiguous and avoids confusion with the search variable right.
• Two-pointer tie-breaking error — using >= in abs(arr[left] - x) >= abs(arr[right] - x) removes from the left on ties, which discards the smaller element; the condition must be strict > so ties fall through to remove from the right.

Related Problems

• kth-largest-element-in-an-array — k-selection concept without the sorted-array structure; uses quickselect or a heap instead of a sliding window
• k-closest-points-to-origin — same k-closest pattern applied to 2D Euclidean distance, where a heap or quickselect replaces binary search
• kth-smallest-element-in-a-bst — exploiting a BST's sorted structure to find the k-th closest to the minimum via in-order traversal
• find-peak-element — binary search where the partition compares adjacent elements; the same left/right boundary narrowing template applies
• koko-eating-bananas — binary search on the answer value rather than the array index; builds intuition for choosing the right search space