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.
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.
We initiate a binary search between 0 and len(arr) - k. Depending on whether the element x is closer to the left or right side, we move the binary search mid-point. Once the position is found, the array is sliced from left to left + k to get the result.
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.
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.
Using two pointers from both ends of the array, we check which value is closer to x and move the respective pointer inwards until only k elements are left. These k elements will be the closest to x.
Time Complexity: O(n). Space Complexity: O(k).
| Approach | Complexity |
|---|---|
| Binary Search with Sliding Window | 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. |
| Two Pointers | Time Complexity: O(n). Space Complexity: O(k). |
| Sort | — |
| Binary search | — |
| Default Approach | — |
| 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 |
Find K Closest Elements - Leetcode 658 - Python • NeetCode • 110,341 views views
Watch 9 more video solutions →Practice Find K Closest Elements with our built-in code editor and test cases.
Practice on FleetCode