Leetcode 658. Find K Closest Elements

Problem Explanation

In this problem, we are given a sorted list of integers, and two integers 'k' and 'x'. We have to return 'k' number of closest elements to 'x' from the sorted list.

The elements returned should be sorted in ascending order, and in case of a tie (two elements at the same distance from 'x'), the smaller element is preferred.

For example, if we have [1,2,3,4,5] as the sorted list of integers, 'k' = 4 and 'x' = 3. The closest elements to 'x' = 3 are [1,2,3,4]. These 4 elements are closest to the 'x' = 3.

In the solution, we use a binary search approach to identify the elements closest to 'x'.

Walkthrough and Approach

Let's take the above example:

1Array = [1, 2, 3, 4, 5], k = 4, x = 3

We initialise two pointers 'l' and 'r', to the beginning and the end-k of the Array.

1l = 0, r = Array size - k = 1, mid = (l + r) // 2 = 0 

We then go into a while loop until 'l' < 'r'. Within this loop, we find the mid (m = (l + r) / 2). We then check whether the difference between 'x' and the element at 'mid' is lesser than or equal to the difference between element at 'mid + k' and 'x'.

If it is True, we move the right pointer 'r' to 'm'. If it is False, we move the left pointer 'l' to 'm + 1'.

By doing this, we are essentially moving our window of 'k' elements towards 'x'.

Once we break out of the loop, we will have 'l' pointing at the first element of the 'k' close elements to 'x'. We return the 'k' elements starting from 'l'.

Python Solution

1
2python
3class Solution:
4    def findClosestElements(self, arr, k, x):
5        left, right = 0, len(arr) - k
6        while left < right:
7            mid = (left + right) // 2
8            if x - arr[mid] > arr[mid + k] - x:
9                left = mid + 1
10            else:
11                right = mid
12        return arr[left:left + k]

Java Solution

1
2java
3class Solution {
4    public List<Integer> findClosestElements(int[] arr, int k, int x) {
5        int left = 0, right = arr.length - k;
6        while (left < right) {
7            int mid = (left + right) / 2;
8            if (x - arr[mid] > arr[mid + k] - x) {
9                left = mid + 1;
10            } else {
11                right = mid;
12            }
13        }
14        List<Integer> result = new ArrayList<>();
15        for (int i = 0; i < k; i++) {
16            result.add(arr[left + i]);
17        }
18        return result;
19    }
20}

JavaScript Solution

1
2javascript
3class Solution {
4    findClosestElements(arr, k, x) {
5        let left = 0, right = arr.length - k;
6        while (left < right) {
7            let mid = Math.floor((left + right) / 2);
8            if (x - arr[mid] > arr[mid + k] - x) {
9                left = mid + 1;
10            } else {
11                right = mid;
12            }
13        }
14        return arr.slice(left, left + k);
15    }
16}

C++ Solution

1
2c++
3class Solution {
4public:
5    vector<int> findClosestElements(vector<int>& arr, int k, int x) {
6        int left = 0, right = arr.size() - k;
7        while (left < right) {
8            int mid = (left + right) / 2;
9            if (x - arr[mid] > arr[mid + k] - x) {
10                left = mid + 1;
11            } else {
12                right = mid;
13            }
14        }
15        return vector<int>(arr.begin() + left, arr.begin() + left + k);
16    }
17};

C# Solution

1
2csharp
3public class Solution {
4    public IList<int> FindClosestElements(int[] arr, int k, int x) {
5        int left = 0, right = arr.Length - k;
6        while (left < right) {
7            int mid = (left + right) / 2;
8            if (x - arr[mid] > arr[mid + k] - x) {
9                left = mid + 1;
10            } else {
11                right = mid;
12            }
13        }
14        return arr.Skip(left).Take(k).ToList();
15    }
16}

These solutions show how to implement a binary search algorithm in different programming languages to solve this problem of finding the closest elements in a sorted array. The primary components include initializing pointers at specific positions in the array, implementing a while loop to continuously narrow down the search area by comparing the differences between 'x' and the element at 'mid', and finally when the loop breaks, returning the 'k' closest elements to 'x'.

In all implemented languages, the concept and logic applied is similar with syntax differences. However, each language has its unique way of presenting the solution according to its standard library predicates and functions. The solutions leverage array slicing, list construction, vector casting and 'skip and take' method to accomplish the final goal of returning the 'k' closest elements in the respective languages.

In Python, we return a slice of the list from 'left' index to 'left+k'.

In Java, we use a for loop to add each of the 'k' closest elements to a new Integer list.

In JavaScript, we return a slice of the array from 'left' to 'left+k'.

In C++, we return a vector constructed from the iterator 'arr.begin() + left' and 'arr.begin() + left + k'.

In C#, we use the 'Skip' and 'Take' LINQ methods to select 'k' elements starting from the 'left' index.

Thus each solution, while following similar algorithmic steps, utilizes the unique capabilities and functions of their respective languages to achieve the desired result. This goes to show the flexibility and adaptability needed when switching between different programming languages.


Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.


TA 👨‍🏫