In this guide, you will get 658. Find K Closest Elements LeetCode Solution with the best time and space complexity. The solution to Find K Closest Elements problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
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,1,2,3,4,5], k = 4, x = -1
Output: [1,1,2,3]
Constraints:
1 <= k <= arr.length
1 <= arr.length <= 104
arr is sorted in ascending order.
-104 <= arr[i], x <= 104
Complexity Analysis
Time Complexity: O(\log(n – k) + k)
Space Complexity: O(k)
658. Find K Closest Elements LeetCode Solution in C++
class Solution {
public:
vector<int> findClosestElements(vector<int>& arr, int k, int x) {
int l = 0;
int r = arr.size() - k;
while (l < r) {
const int m = (l + r) / 2;
if (x - arr[m] <= arr[m + k] - x)
r = m;
else
l = m + 1;
}
return {arr.begin() + l, arr.begin() + l + k};
}
}; /* code provided by PROGIEZ */
658. Find K Closest Elements LeetCode Solution in Java
class Solution {
public List<Integer> findClosestElements(int[] arr, int k, int x) {
int l = 0;
int r = arr.length - k;
while (l < r) {
final int m = (l + r) / 2;
if (x - arr[m] <= arr[m + k] - x)
r = m;
else
l = m + 1;
}
return Arrays.stream(arr, l, l + k).boxed().collect(Collectors.toList());
}
} // code provided by PROGIEZ
658. Find K Closest Elements LeetCode Solution in Python
class Solution:
def findClosestElements(self, arr: list[int], k: int, x: int) -> list[int]:
l = 0
r = len(arr) - k
while l < r:
m = (l + r) // 2
if x - arr[m] <= arr[m + k] - x:
r = m
else:
l = m + 1
return arr[l:l + k] # code by PROGIEZ
