Watch 10 video solutions for Find K Closest Elements, a medium level problem involving Array, Two Pointers, Binary Search. This walkthrough by NeetCode has 110,341 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.length1 <= arr.length <= 104arr is sorted in ascending order.-104 <= arr[i], x <= 104Problem Overview: Given a sorted array arr, an integer k, and a target x, return the k elements closest to x. If two numbers are equally close, the smaller value is preferred. The result must also remain sorted.
Approach 1: Two Pointers Shrinking Window (O(n) time, O(1) space)
This method keeps a window covering the entire array and repeatedly removes the element that is farther from x. Start with two pointers: left = 0 and right = n - 1. While the window size is larger than k, compare |arr[left] - x| and |arr[right] - x|. Remove the element with the larger distance by moving the corresponding pointer inward. Because the array is already sorted, the remaining window of size k is guaranteed to contain the closest elements. This approach uses the Two Pointers technique and works well when simplicity matters more than optimal logarithmic performance.
Approach 2: Binary Search with Sliding Window (O(log(n-k)) + O(k) time, O(1) space)
The array is sorted, which allows you to binary search the starting index of the optimal window of size k. Instead of searching for a single element, search the range [0, n-k]. For a candidate start mid, compare x - arr[mid] with arr[mid + k] - x. If the left side is larger, the window should move right; otherwise it should stay left. This works because the relative distances determine which side of the window is farther from x. After binary search finishes, the subarray arr[left : left + k] contains the answer. The window behaves like a fixed-size Sliding Window while binary search narrows the correct position using the properties of a sorted Binary Search space.
Recommended for interviews: Binary Search with Sliding Window is the expected optimal solution. It reduces the search space to log(n-k) comparisons and avoids scanning the whole array. Interviewers often accept the two-pointer shrinking approach first because it shows understanding of distance comparison, but the binary search optimization demonstrates stronger algorithmic reasoning on sorted arrays.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Two Pointers Shrinking Window | O(n) | O(1) | When the array is sorted and you want a straightforward implementation without binary search |
| Binary Search + Sliding Window | O(log(n-k)) + O(k) | O(1) | Best choice for large arrays where you want the optimal logarithmic search |