Find K Closest Elements — Solution in Python, Java & C++
Find K Closest Elements solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
Find K Closest Elements is a medium coding problem on arrays, sorting and binary search, asked in Amazon, Google and Meta interviews.
- Difficulty: Medium
- Topics: Arrays, Sorting, Binary Search, Two Pointers, Heap
- Asked at: Amazon, Google, Meta
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
Given a sorted integer array arr, and two integers k and x, return the k elements closest to x, sorted ascending.
An element a is closer than b when |a - x| < |b - x|, or when the distances tie 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]
Example 3
Input: arr = [1,1,2,3,4,5], k = 4, x = -1
Output: [1,1,2,3]
Constraints
1 <= k <= arr.length <= 401 <= arr[i], x <= 10000arr is sorted in ascending order.
Hints for Find K Closest Elements
Hint 1
The answer is a contiguous window of length
k— the array is sorted, so the closest elements sit together.Hint 2
Binary search for the window's left edge among
0 … n - k.Hint 3
Compare
x - arr[mid]witharr[mid + k] - x: if the left edge is further away, slide right.
How to solve Find K Closest Elements
The answer is a contiguous window of length k; binary search its left edge in 0 .. n - k by comparing the distance of the window's left end with the element just past its right end.
Approach
- Set
lo = 0,hi = n - k. - While
lo < hi:mid = (lo + hi) / 2; ifx - arr[mid] > arr[mid + k] - x,lo = mid + 1; elsehi = mid. - Return
arr[lo : lo + k].
Why it works
Sliding the window right swaps arr[mid] for arr[mid + k], which is an improvement exactly when the left element is further from x (ties keep the smaller value). That predicate is monotone in mid, so binary search finds the optimal edge.
Complexity
- Time —
O(log(n - k) + k) - Space —
O(k)
Pitfalls
- Use
>not>=so ties prefer the left window, matching the "smaller wins" rule.
Reference solution
Python
def findClosestElements(arr, k: int, x: int):
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]Java
public static int[] findClosestElements(int[] arr, int k, int x) {
int lo = 0, hi = arr.length - k;
while (lo < hi) {
int mid = (lo + hi) / 2;
if (x - arr[mid] > arr[mid + k] - x) lo = mid + 1;
else hi = mid;
}
return Arrays.copyOfRange(arr, lo, lo + k);
}C++
vector<int> findClosestElements(vector<int>& arr, int k, int x) {
int lo = 0, hi = (int) arr.size() - k;
while (lo < hi) {
int mid = (lo + hi) / 2;
if (x - arr[mid] > arr[mid + k] - x) lo = mid + 1;
else hi = mid;
}
return vector<int>(arr.begin() + lo, arr.begin() + lo + k);
}JavaScript
var findClosestElements = function(arr, k, x) {
let lo = 0, hi = arr.length - k;
while (lo < hi) {
const mid = Math.floor((lo + hi) / 2);
if (x - arr[mid] > arr[mid + k] - x) lo = mid + 1;
else hi = mid;
}
return arr.slice(lo, lo + k);
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Sorting Algorithms