Find K Closest Elements

Problem

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

An integer a is closer to x than an integer b if:

|a - x| < |b - x|, or
|a - x| == |b - x| and a < b

Example 1:

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

Example 2:

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

Constraints:

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

Solution

/**
 * @param {number[]} arr
 * @param {number} k
 * @param {number} x
 * @return {number[]}
 */
var findClosestElements = function(arr, k, x) {
    // binary search
    let index = searchInsert(arr, x);
    let l = index;
    let r = index;

    // two pointer
    while (r - l <= k) {
        const a = arr[l];
        const b = arr[r];
        if (l < 0) {
            r++;
        } else if (r >= arr.length) {
            l--;
        } else if (Math.abs(a - x) <= Math.abs(b - x)) {
            l--;
        } else {
            r++;
        }
    }

    // slice arr in range (l, r)
    return arr.slice(l + 1, r);
};

// find index of target in arr or its insertion index
var searchInsert = function(nums, target) {
    let lo = 0;
    let hi = nums.length - 1;

    while (lo <= hi) {
        const mid = Math.floor((lo + hi) / 2);
        const val = nums[mid];
        if (val < target) {
            lo = mid + 1;
        } else if (val > target) {
            hi = mid - 1;
        } else {
            return mid;
        }
    }
    return lo;
};

We will first locate the insertion position of x in arr using binary search. Next, starting from the insertion position, we use two pointers l and r to slide left and right as needed until indices in the range of (l, r) contains the k closest integers to x.

Problem​

Solution​

Problem

Solution