Last updated on February 12th, 2025 at 02:25 am
Here, we see a Find K Closest Elements LeetCode Solution. This Leetcode problem is solved using different approaches in many programming languages, such as C++, Java, JavaScript, Python, etc.
List of all LeetCode Solution
Topics
Companies
Level of Question
Medium
Find K Closest Elements LeetCode Solution
Table of Contents
1. Problem Statement
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]
2. Coding Pattern Used in Solution
The coding pattern used in the provided code is “Modified Binary Search” for the Python code and “Two Pointers” for the Java and JavaScript code. The C++ code uses a “Top ‘K’ Elements” pattern because it leverages a priority queue (min-heap) to find the closest elements.
3. Code Implementation in Different Languages
3.1 Find K Closest Elements C++
class Solution {
public:
vector<int> findClosestElements(vector<int>& arr, int k, int x) {
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
for (int i = 0; i < arr.size(); i++)
pq.push({abs(arr[i] - x), arr[i]});
vector<int> ans;
for (int i = 0; i < k; i++)
{
ans.push_back(pq.top().second);
pq.pop();
}
sort(ans.begin(), ans.end());
return ans;
}
};
3.2 Find K Closest Elements Java
class Solution {
public List<Integer> findClosestElements(int[] arr, int k, int x) {
int start = 0;
int end = arr.length - 1;
while (end - start >= k) {
if (Math.abs(arr[start] - x) > Math.abs(arr[end] - x)) {
start++;
} else {
end--;
}
}
List<Integer> result = new ArrayList<>(k);
for (int i = start; i <= end; i++) {
result.add(arr[i]);
}
return result;
}
}
3.3 Find K Closest Elements JavaScript
var findClosestElements = function (arr, k, x) {
let leftPointer = 0;
let rightPointer = arr.length - 1;
while (rightPointer - leftPointer >= k) {
if (Math.abs(arr[leftPointer] - x) <= Math.abs(arr[rightPointer] - x)) rightPointer--;
else leftPointer++;
}
return arr.slice(leftPointer, rightPointer + 1);
};
3.4 Find K Closest Elements Python
class Solution(object):
def findClosestElements(self, arr, k, x):
lo, hi = 0, len(arr)-k
while lo<hi:
mid = (lo + hi)//2
if x-arr[mid]>arr[mid+k]-x:
lo = mid + 1
else:
hi = mid
return arr[lo:lo+k]
4. Time and Space Complexity
| Time Complexity | Space Complexity | |
| C++ | O(n log n) | O(n) |
| Java | O(n) | O(k) |
| JavaScript | O(n) | O(1) |
| Python | O(log(n-k) + k) | O(1) |