Find K Closest Elements - Solution & Explanation
Problem Statement
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|anda < 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 <= 104arris sorted in ascending order.-104 <= arr[i], x <= 104
Approach Overview
Problem 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 1: Binary Search with Sliding Window
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.
Complexity
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.
Approach 2: Two Pointers
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.
Complexity
Time Complexity: O(n). Space Complexity: O(k).
Approach 3: Sort
Try this approach in the editor →Approach 4: Binary search
Try this approach in the editor →Approach 5: Default Approach
Try this approach in the editor →Complexity Comparison
| 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 | — |
Detailed Complexity Analysis
| 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 |
Video Solution
Find K Closest Elements - Leetcode 658 - Python • NeetCode • 116,582 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Find K Closest Elements easy or hard?
Find K Closest Elements Python or Java solution?
How to solve Find K Closest Elements in O(log n)?
What is the best approach for Find K Closest Elements?
What data structure is used in Find K Closest Elements?
What is the time complexity of Find K Closest Elements?
Is Find K Closest Elements asked at Google, Amazon, or Meta?
Ready to solve this problem?
Practice Find K Closest Elements with our built-in code editor and test cases.
Practice on FleetCode