Find K Closest Elements

Problem Statement

Given a sorted array arr, an integer k, and a value x, return the k elements closest to x, in ascending order. Ties prefer the smaller element.

Example

Input:  arr = [1,2,3,4,5], k = 4, x = 3
Output: [1,2,3,4]

Approach

The answer is a contiguous window of length k. Binary search its start in [0, n-k]. Compare the gap at the two edges: if x - arr[mid] > arr[mid+k] - x, the window should move right (left = mid+1), otherwise left (right = mid). Return the window.

Complexity

• Time: O(log(n - k) + k)
• Space: O(1) extra

Solution Code

Python

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

Java

List<Integer> findClosestElements(int[] arr, int k, int x) {
    int left = 0, right = arr.length - k;
    while (left < right) {
        int mid = left + (right - left) / 2;
        if (x - arr[mid] > arr[mid + k] - x) left = mid + 1;
        else right = mid;
    }
    List<Integer> res = new ArrayList<>();
    for (int i = left; i < left + k; i++) res.add(arr[i]);
    return res;
}

C++

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

Key Takeaways

• Binary-search the window start, not an element.
• Comparing the two edge gaps handles the tie-breaking toward smaller values.
• Reference: LeetCode 658 (Find K Closest Elements).