Find K Closest Elements — BS on Left Window Boundary

Problem 320 · Find K Closest Elements

Difficulty: Medium · Pattern: BS on Window Position

Find k elements closest to x. Among equal distance, prefer smaller.

Intuition

Binary search for the left index lo of the window [lo, lo+k-1]. Compare x - arr[mid] vs arr[mid+k] - x.

Solutions

# Python
def findClosestElements(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]

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

Complexity

Time: O(log(n-k) + k)
Space: O(1) excluding output