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 < bExample 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.length1 <= arr.length <= 104arr is sorted in ascending order.-104 <= arr[i], x <= 104The goal of #658 Find K Closest Elements is to return the k elements in a sorted array that are closest to a given value x. Because the array is already sorted, efficient approaches can leverage binary search and two pointers instead of checking every combination.
A common strategy is to use binary search to locate the best starting position of a window of size k. By comparing the distance between x and the boundaries of candidate windows, we can shift the window left or right until the optimal segment is found. This approach works because the array order guarantees that the closest elements will form a contiguous block.
Another idea uses two pointers expanding from the insertion position of x, gradually selecting the closer side until k elements are chosen. Heap-based solutions also exist but are usually less efficient.
The binary search window approach typically runs in O(log(n − k)) time with O(1) extra space, making it the preferred method for large arrays.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Binary Search + Sliding Window | O(log(n - k)) | O(1) |
| Two Pointers Expansion | O(k + log n) | O(1) |
| Max/Min Heap (Priority Queue) | O(n log k) | O(k) |
NeetCode
This approach uses binary search to find the position where x would fit in the array or where it is located. From this point, a sliding window is expanded to the left and right to check k closest elements. Given the sorted nature of the array, this is efficient.
Time Complexity: O(log(n-k) + k) where n is the length of the array, and we are moving a window over it. Space Complexity: O(k) for storing the resulting subarray.
1import java.util.*;
2
3class Solution {
4 public List<Integer> findClosestElements(int[] arr, int k,This is Java's implementation of the binary search approach. Arrays and ArrayList are utilized to handle subarray extraction post binary search index determination.
This approach initiates two pointers from the start and end of the array and gradually closes inwards by comparing the distance from x from both ends until the closest k elements are left. This is linear after the search initialization.
Time Complexity: O(n). Space Complexity: O(k).
1#include
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, variations of this problem frequently appear in technical interviews at major tech companies. It tests understanding of binary search, sliding window techniques, and how to exploit sorted arrays for optimal performance.
The optimal approach uses binary search to locate the best starting index of a window of size k. By comparing distances between x and the window boundaries, the algorithm shifts the window until the closest segment is found. This method achieves O(log(n-k)) time complexity with constant extra space.
Because the input array is sorted, elements closer to x will appear near each other. If a farther element is included while a closer one is skipped, the ordering would contradict the sorted structure. Therefore the final k closest elements always form a continuous window.
A heap or priority queue can be used to track the k closest elements while scanning the array. However, this approach is typically less efficient than binary search since it requires O(n log k) time. It is still useful when the array is not sorted.
The C solution involves sorting the array twice, initially to rearrange by distance from x, and subsequently on the first k entries. This may not be the most efficient solution, with O(n log n) complexity.