Solution: Find K Closest Elements

Statement

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

An integer, nums[i], is considered to be closer to target, as compared to nums[j] when |nums[i] - target| $<$ |nums[j] - target|. However, when |nums[i] - target| $=$ |nums[j] - target|, the smaller of the two values is selected.

Constraints:

• $1 \leq$ k $\leq$ nums.length
• $1 \leq$ nums.length $\leq 10^3$
• nums is sorted in ascending order.
• $-10^4 \leq$ nums[i], target $\leq 10^4$

Solution

So far, you’ve probably brainstormed some approaches and have an idea of how to solve this problem. Let’s explore some of these approaches and figure out which one to follow based on considerations such as time complexity and any implementation constraints.

Naive approach

The k closest integers to target are those integers of nums that have the minimum distance from target, and this distance is the absolute difference between the integer and target.

In the naive approach, we first compute the distance of every element of nums from the given target. We store these distances along with the elements themselves as pairs in a new array, distances, that is, each pair will consist of the absolute difference and the corresponding element from nums. Now, we sort distances based on the absolute differences in ascending order. However, if any two pairs have the same absolute difference, sort them based on the element value in ascending order. Next, we iterate through the sorted distances to extract and store the required k elements in a new array, result. Finally, we sort result and return it as the output.

For example, if nums = [1, 2, 3, 4], target = 3, and k = 2, then distances = [(2, 1), (1, 2), (0, 3), (1, 4)]. It will get sorted like this: [(0, 3), (1, 2), (1, 4), (2, 1)]. Now, pick the first two elements, i.e., result = [3, 2]. Sort result to get the valid output, i.e., [2, 3].

We traverse the complete array to calculate the distance of each element in nums from target, so it takes $O(n)$ ...