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 <= 104This 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.
C++
Java
C#
JavaScript
C
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.
C++
Java
C#
JavaScript
C
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). |
Find K Closest Elements - Leetcode 658 - Python • NeetCode • 86,968 views views
Watch 9 more video solutions →Practice Find K Closest Elements with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor