AlgoMaster Logo

Find K Closest Elements

mediumUpdated September 21, 2026

Understanding the Problem

We have a sorted array and we need to find a window of k elements closest to a given value x. The answer is always k consecutive elements, and that fact drives every efficient solution.

Here is why the answer must be contiguous. Suppose elements a and b are both in the answer, with a < b. Then every element c between them (a < c < b) must also be in the answer, because c is at least as close to x as the farther of a and b. So we can never have a gap. The answer is a contiguous subarray of length k, and the problem reduces to finding the best starting index of that window.

The tie-breaking rule, prefer the smaller element when distances are equal, favors the left side of the window. When |arr[i] - x| equals |arr[j] - x| and arr[i] < arr[j], we pick arr[i].

Key Constraints:

  • arr is sorted in ascending order → Sorting is already done for us. This opens the door to binary search and two-pointer techniques that depend on order.
  • 1 <= k <= arr.length → k is always valid, so a window of size k always fits inside the array. No edge case where k exceeds n.
  • -10^4 <= arr[i], x <= 10^4 → Distances like arr[i] - x stay within [-2 10^4, 2 10^4], so a 32-bit int holds every intermediate value without overflow.

Approach 1: Sort by Distance

Intuition

Compute the distance from each element to x, sort the array by that distance, take the first k elements, then sort those k elements back into ascending order.

This ignores the sorted structure of the input and does more work than necessary, but it is short and correct, which makes it a useful baseline before we optimize.

Algorithm

  1. Create a copy of the array (or create index-distance pairs).
  2. Sort this copy by the absolute distance to x. Use the tie-breaking rule: if two elements have the same distance, the smaller one comes first.
  3. Take the first k elements from this sorted copy.
  4. Sort those k elements in ascending order.
  5. Return the result.

Visualization and Code

Loading animation...

This approach pays O(n log n) for sorting even though the input is already sorted. Because the answer is a contiguous window, the next approach locates its boundaries directly in linear time.

Approach 2: Two Pointers (Shrink from Ends)

Intuition

Start with the entire array and repeatedly remove the element farthest from x. After removing n - k elements, what remains is the answer.

Because the answer is a contiguous subarray, the farthest element is always at one of the two ends. At each step, compare the leftmost and rightmost elements. Remove whichever is farther from x. If they are equally far, remove the rightmost one, since we prefer smaller elements for ties.

Algorithm

  1. Initialize left = 0 and right = arr.length - 1.
  2. While right - left + 1 > k (the window is bigger than k):
    • Compare the distance from arr[left] to x with the distance from arr[right] to x.
    • If x - arr[left] > arr[right] - x, the left end is farther, so move left right.
    • Otherwise, the right end is farther (or tied), so move right left.
  3. Return the subarray from left to right (inclusive).

Visualization and Code

Loading animation...

The two-pointer approach removes elements one at a time, taking O(n - k) steps. When n is large and k is small, that is close to a full linear scan. Binary search on the window's starting index narrows it down in logarithmic time.

Approach 3: Binary Search on Left Bound (Optimal)

Intuition

A contiguous window of length k is fully determined by its starting index, which lies in the range [0, n - k]. Finding the answer means finding the best starting index in that range.

For a candidate start mid, the window is arr[mid..mid+k-1]. The element just past the window's right edge is arr[mid + k]. Compare the distance of the leftmost in-window element, x - arr[mid], with the distance of that next element, arr[mid + k] - x. If x - arr[mid] > arr[mid + k] - x, then arr[mid] is farther from x than arr[mid + k], so sliding the window one step right (dropping arr[mid], gaining arr[mid + k]) cannot hurt and may help. We move the search right. Otherwise the window starting at mid is at least as good, so we keep it as a candidate and search left.

This comparison defines a monotonic boundary: once shifting right stops helping, it never starts helping again, which is what makes binary search valid here.

Algorithm

  1. Set left = 0 and right = arr.length - k.
  2. While left < right:
    • Compute mid = left + (right - left) / 2.
    • If x - arr[mid] > arr[mid + k] - x, the left boundary needs to move right: set left = mid + 1.
    • Otherwise, the window starting at mid is a candidate: set right = mid.
  3. Return the subarray arr[left..left+k-1].

Visualization and Code

Loading animation...