Find K Closest Elements

medium array two pointers binary search

Problem

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

Inputarr = [1, 2, 3, 4, 5], k = 4, x = 3

Output[1, 2, 3, 4]

Binary search for the optimal length-k window start.

arr (sorted, comma-separated)

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

function findClosestElements(arr, k, x) {
  let lo = 0, hi = arr.length - k;
  while (lo < hi) {
    const mid = (lo + hi) >> 1;
    if (x - arr[mid] > arr[mid + k] - x) lo = mid + 1;
    else hi = mid;
  }
  return arr.slice(lo, lo + k);
}

class Solution {
    public List<Integer> findClosestElements(int[] arr, int k, int x) {
        int lo = 0, hi = arr.length - k;
        while (lo < hi) {
            int mid = (lo + hi) >>> 1;
            if (x - arr[mid] > arr[mid + k] - x) lo = mid + 1;
            else hi = mid;
        }
        List<Integer> out = new ArrayList<>();
        for (int i = lo; i < lo + k; i++) out.add(arr[i]);
        return out;
    }
}

vector<int> findClosestElements(vector<int>& arr, int k, int x) {
    int lo = 0, hi = (int) arr.size() - k;
    while (lo < hi) {
        int mid = (lo + hi) / 2;
        if (x - arr[mid] > arr[mid + k] - x) lo = mid + 1;
        else hi = mid;
    }
    return vector<int>(arr.begin() + lo, arr.begin() + lo + k);
}

Explanation

Because the answer is always k consecutive elements of a sorted array, we don't pick elements one by one — we just pick the best window of length k. There are n - k + 1 possible window starts, and we binary search for the best one.

We keep lo = 0 and hi = len(arr) - k as the range of possible start indices. At each step we test the middle start mid by comparing the two edges of that window: x - arr[mid] (how far x is from the left edge) versus arr[mid + k] - x (how far x is from the element just past the right edge).

If the left distance is bigger, the window is reaching too far left, so a window starting further right would be closer: we move lo = mid + 1. Otherwise the current start is good enough or we should go left, so hi = mid. When lo meets hi, that's the best start, and we return arr[lo:lo + k].

The result is automatically in ascending order since we slice a contiguous block of the sorted array.

Example: arr = [1, 2, 3, 4, 5], k = 4, x = 3. The search settles on start index 0, giving the window [1, 2, 3, 4], which are indeed the four closest values to 3.

Time: O(log(n − k)) Space: O(k) output