Find K Closest Elements

You are given a sorted array of integers, nums, and two integers, target and k. Your task is to return k integers from nums that are the closest to target. The integers in the output should be in sorted order.

Find K Closest Elements

Problem Statement

You are given a sorted array of integers, nums, and two integers, target and k. Your task is to return k integers from nums that are the closest to target. The integers in the output should be in sorted order.

An integer nums[i] is considered closer to target than nums[j] when:

• |nums[i] - target| < |nums[j] - target|

However, if both distances are equal (|nums[i] - target| == |nums[j] - target|), the smaller of the two values is chosen.

Constraints

• 1 ≤ k ≤ nums.length
• 1 ≤ nums.length ≤ 10³
• nums is sorted in ascending order.
• −10⁴ ≤ nums[i], target ≤ 10⁴

Solution

Since nums is already sorted, we can start by finding the element closest to target, and then build a window of size k around it.

Steps

• First, we handle a few simple cases directly:
  • If the array's length already equals k, we just return the whole array.
  • If target is less than or equal to the first element, the closest k elements are simply the first k elements of the array.
  • If target is greater than or equal to the last element, the closest k elements are the last k elements of the array.
• Otherwise, we find the position of the element closest to target using binary search. This gives us a starting point.
• We then set up a small window, just one step wide at first, right around this closest position.
• We grow the window one step at a time, until it reaches size k:
  • We compare the element just outside the window on the left with the element just outside the window on the right.
  • Whichever one is closer to target (or equally close but smaller), we bring it into the window.
  • If the left side has run out of elements (windowLeft === -1), we can only expand to the right.
  • If the right side has run out of elements, we can only expand to the left.
• Once the window reaches size k, we return the elements inside it.

Code

function findClosestElements(nums, k, target) {
    if (nums.length === k) {
        return nums;
    }

    if (target <= nums[0]) {
        return nums.slice(0, k);
    }

    if (target >= nums[nums.length - 1]) {
        return nums.slice(nums.length - k);
    }

    const firstClosest = binarySearch(nums, target);

    let windowLeft = firstClosest - 1;
    let windowRight = windowLeft + 1;

    while (windowRight - windowLeft - 1 < k) {
        if (windowLeft === -1) {
            windowRight++;
            continue;
        }

        if (windowRight === nums.length || Math.abs(nums[windowLeft] - target) <= Math.abs(nums[windowRight] - target)) {
            windowLeft--;
        }
        else {
            windowRight++;
        }
    }

    return nums.slice(windowLeft + 1, windowRight);
}