Community Problem

Find K Closest Elements

Difficulty: Medium

Find a length-k window in a sorted array whose elements are closest to x, using a binary search on the LEFT edge of the window.

Find K Closest Elements

Find a length-k window in a sorted array whose elements are closest to x, using a binary search on the LEFT edge of the window.

MEDIUM

Free

binary-search

two-pointers

arrays

By @jameszhang

January 20, 2026

Updated May 20, 2026

786 views

4.5 (14)

I see candidates default to the heap solution on this one and the interviewer always asks the follow-up: can you do it in O(log n + k) instead of O(n log k)? The trick is realizing the answer is a contiguous window and binary-searching for the WINDOW LEFT EDGE, not for the value of x. That reframing is the whole insight.

Find K Closest Elements

Given a sorted integer array arr, two integers k and x, return the k closest integers to x in the array. The result must be sorted in ascending order.

An integer a is closer to x than b if |a - x| < |b - x|. Ties break in favor of the smaller value: |a - x| == |b - x| and a < b makes a closer.

Examples

Example 1:

Input: arr = [1, 2, 3, 4, 5], k = 4, x = 3
Output: [1, 2, 3, 4]
Explanation: All five elements differ by at most 2 from 3, but the window [1, 2, 3, 4] has total absolute distance 4 vs [2, 3, 4, 5] total 4. Tie breaks toward smaller values, so the left window wins.

Example 2:

Input: arr = [1, 2, 3, 4, 5], k = 4, x = -1
Output: [1, 2, 3, 4]
Explanation: All elements are >= -1, so the closest k start at the left.

Example 3:

Input: arr = [1, 1, 1, 10, 10, 10], k = 1, x = 9
Output: [10]
Explanation: 10 is at distance 1 from 9; any 1 is at distance 8.

Example 4:

Input: arr = [0, 0, 1, 2, 3, 3, 4, 7, 7, 8], k = 3, x = 5
Output: [3, 3, 4]
Explanation: Closest three are 3, 3, 4. The 7 is at distance 2, but 4 is at distance 1, so 4 wins; second 3 is at distance 2, equal to 7, tie breaks to the smaller value.

Constraints

1 <= k <= arr.length
1 <= arr.length <= 10^4
arr is sorted in ascending order.
-10^4 <= arr[i], x <= 10^4

Follow-up

The heap solution is O(n log k). Can you do it in O(log n + k)? Hint: the answer is a contiguous window of length k. Binary-search for the left edge of that window in the index range [0, arr.length - k].

Solution

JavaScript

Python

Hints

0/4

Hint 1

Hint 2

Hint 3

Hint 4

Solution Walkthrough

Approach

The key reframing: the answer is a contiguous window of length k (because the array is sorted, the k closest elements to x form a contiguous slice). So we are not searching for x in the array; we are searching for the optimal LEFT edge of that window in the index range [0, n - k].

Key insight

For a candidate left edge i, the window is [i, i + k - 1] and its right neighbor outside the window is arr[i + k]. Slide the window one step right by deciding which is closer to x: the leftmost element arr[i] (currently inside) or arr[i + k] (currently outside). The element with the smaller distance should stay (or enter) the window; the element with the larger distance should leave.

Formally: if x - arr[mid] > arr[mid + k] - x, the LEFT endpoint is farther than the would-be right entrant, so shifting the window right strictly improves the total distance. Otherwise the current mid is at least as good, so the optimal left edge is <= mid.

Algorithm

Set lo = 0, hi = n - k.
While lo < hi:
- mid = lo + (hi - lo) // 2.
- If x - arr[mid] > arr[mid + k] - x: lo = mid + 1.
- Else: hi = mid.
Return arr.slice(lo, lo + k).

Complexity

Text

Metric  Value
------  --------------
Time    O(log(n - k) + k)
Space   O(k) for the result slice; O(1) auxiliary

The binary search runs in O(log(n - k)) and the final slice copy is O(k).

Why it works

The sum of distances sum_{j in window} |arr[j] - x| is a convex function of the window's left edge over [0, n - k]. At the optimum, sliding right increases the total (the new entrant is farther than the leaving element) and sliding left also increases the total. The pairwise comparison (x - arr[mid]) vs (arr[mid + k] - x) is exactly the directional derivative; we move toward the side that decreases.

The tie-break rule (<= keeps the left-er window) automatically gives the smaller-value preference required by the problem statement, because at equality arr[mid] == 2x - arr[mid + k], the left window has the smaller starting value.

Pitfalls

Comparing absolute distances Math.abs(arr[mid] - x) vs Math.abs(arr[mid + k] - x) introduces a tie-breaking bug. Use x - arr[mid] and arr[mid + k] - x directly; both are non-negative if x is between arr[mid] and arr[mid + k], which is the only case where the comparison decides. When x < arr[mid], the left side is negative but the right side is positive and definitely larger, so > is false and we shrink right correctly.
Searching the value space instead of the index space. The trick of this problem is the index-space binary search; do not lower_bound for x and then expand a window with two pointers (that is O(log n + k) too but more error-prone).
Off-by-one on hi = arr.length - k. The maximum valid left edge is arr.length - k, so the half-open template uses hi = arr.length - k (NOT hi = arr.length - k - 1).

Solution Code

All Problems