658. Find K Closest Elements

Find K Closest Elements 

Problem Description

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: (658. Find K Closest Elements)

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

Example 2: (658. Find K Closest Elements)

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

Constraints:

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



Approach) Sorting

/**
 * @param {number[]} arr
 * @param {number} k
 * @param {number} x
 * @return {number[]}
 */
var findClosestElements = function(arr, k, x) {
    let elements = arr.map(val => {
        return {
            val: val,
            dist: Math.abs(val - x)
        };
    });
    
    elements.sort((a, b) => a.dist - b.dist);
    
    return elements.slice(0, k).sort((a, b) => a.val - b.val).map(element => element.val);
};

Approach) Binary Search

Idea:

Binary searching the first index i that arr[i] is closer or equally close to arr[i+k] (Original Post)

Binary searching for x and then expanding to the left and to the right:
The idea is to find the first number which is equal to or greater than x in arr. Then, we determine the indices of the start and the end of a subarray inarr, where the subarray is our result.

The time complexity is O(logn + k)

/**
 * @param {number[]} arr
 * @param {number} k
 * @param {number} x
 * @return {number[]}
 */
/**
 * @param {number[]} arr
 * @param {number} k
 * @param {number} x
 * @return {number[]}
 */
var findClosestElements = function(arr, k, x) {
    let i = 0, j = arr.length - k;
        while (i < j){
            let mid = (i & j) + ((i ^ j) >> 1);

            if(x - arr[mid] > arr[mid + k] - x)
                i = mid + 1;
            else
                j = mid;
        }
        let res = [];
        for (let b = i; b < i + k; ++b) res.push(arr[b]);
        return res;
};

OR

/**
 * @param {number[]} arr
 * @param {number} k
 * @param {number} x
 * @return {number[]}
 */
/**
 * @param {number[]} arr
 * @param {number} k
 * @param {number} x
 * @return {number[]}
 */
var findClosestElements = function(arr, k, x) {
   let left = 0;
    let right = arr.length - k;
    while (left < right) {
        const mid = left + ((right - left) >> 1);
        if (x - arr[mid] > arr[mid + k] - x) {
            left = mid + 1;
        } else {
            right = mid;
        }
    }
    return arr.slice(left, left + k);
};

Conclusion

That’s all folks! In this post, we solved LeetCode problem #658. Find K Closest Elements

I hope you have enjoyed this post. Feel free to share your thoughts on this.

You can find the complete source code on my GitHub repository. If you like what you learn. feel free to fork 🔪 and star ⭐ it.

In this blog, I have tried to collect & present the most important points to consider when improving Data structure and logic, feel free to add, edit, comment, or ask. For more information please reach me here
Happy coding!