Find `k` closest elements to a given value in an array
Given a sorted integer array, find the k closest elements to target in the array where k and target are given positive integers.
The target may or may not be present in the input array. If target is less than or equal to the first element in the input array, return first k elements. Similarly, if target is more than or equal to the last element in the input array, return the last k elements. The returned elements should be in the same order as present in the input array.
For example,
Output: [12, 15, 17, 18]
Input: [2, 3, 4, 5, 6, 7], k = 3, target = 1
Output: [2, 3, 4]
Input: [2, 3, 4, 5, 6, 7], k = 2, target = 8
Output: [6, 7]
The idea is to do a linear search to find the insertion point i. The insertion point is defined as the point at which the key target would be inserted into the array, i.e., the index of the first element greater than the key, or the array’s size if all elements in the array are less than the specified key. Then compare the elements around the insertion point i to get the first k closest elements. The time complexity of this solution is O(n), where n is the size of the input.
We can also find the insertion point i using the binary search algorithm, which runs in O(log(n)) time. Since finding the k closest elements takes O(k) time, the overall time complexity of this solution is O(log(n) + k). Following is the implementation in C, C++, Java, and Python, based on this idea:
C
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 |
#include <stdio.h> #include <stdlib.h> // Function to search the specified array `nums` for key `target` // using the binary search algorithm int binarySearch(int nums[], int n, int target) { int low = 0; int high = n - 1; while (low <= high) { int mid = low + (high - low) / 2; if (nums[mid] < target) { low = mid + 1; } else if (nums[mid] > target) { high = mid - 1; } else { return mid; // key found } } return low; // key not found } // Function to find the `k` closest elements to `target` in a sorted integer array `nums` void findKClosestElements(int nums[], int target, int k, int n) { // find the insertion point using the binary search algorithm int i = binarySearch(nums, n, target); int left = i - 1; int right = i; // run `k` times while (k-- > 0) { // compare the elements on both sides of the insertion point `i` // to get the first `k` closest elements if (left < 0 || (right < n && abs(nums[left] - target) > abs(nums[right] - target))) { right++; } else { left--; } } // print the `k` closest elements left++; while (left < right) { printf("%d ", nums[left]); left++; } } int main(void) { int nums[] = { 10, 12, 15, 17, 18, 20, 25 }; int n = sizeof(nums) / sizeof(nums[0]); int target = 16, k = 4; findKClosestElements(nums, target, k, n); return 0; } |
Output:
12 15 17 18
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 |
#include <iostream> #include <vector> #include <algorithm> using namespace std; // Function to find the `k` closest elements to `target` in a sorted integer vector `input` vector<int> findKClosestElements(vector<int> const &input, int target, int k) { // find the insertion point using the binary search algorithm int i = lower_bound(input.begin(), input.end(), target) - input.begin(); int left = i - 1; int right = i; // run `k` times while (k-- > 0) { // compare the elements on both sides of the insertion point `i` // to get the first `k` closest elements if (left < 0 || (right < input.size() && abs(input[left] - target) > abs(input[right] - target))) { right++; } else { left--; } } // return `k` closest elements return vector<int>(input.begin() + left + 1, input.begin() + right); } int main() { vector<int> input = { 10, 12, 15, 17, 18, 20, 25 }; int target = 16, k = 4; vector<int> result = findKClosestElements(input, target, k); for (int i: result) { cout << i << " "; } return 0; } |
Output:
12 15 17 18
Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 |
import java.util.Arrays; import java.util.Collections; import java.util.List; class Main { // Function to find the `k` closest elements to `target` in a sorted list `input` public static List<Integer> findKClosestElements(List<Integer> input, int k, int target) { // find the insertion point using the binary search algorithm int i = Collections.binarySearch(input, target); // Collections.binarySearch() returns `-(insertion point) - 1` // if the key is not contained in the list if (i < 0) { i = -(i + 1); } int left = i - 1; int right = i; // run `k` times while (k-- > 0) { // compare the elements on both sides of the insertion point `i` // to get the first `k` closest elements if (left < 0 || (right < input.size() && Math.abs(input.get(left) - target) > Math.abs(input.get(right) - target))) { right++; } else { left--; } } // return `k` closest elements return input.subList(left + 1, right); } public static void main(String[] args) { List<Integer> input = Arrays.asList(10, 12, 15, 17, 18, 20, 25); int target = 16, k = 4; System.out.println(findKClosestElements(input, k, target)); } } |
Output:
[12, 15, 17, 18]
Python
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 |
# Function to search the specified array `nums` for key `target` # using the binary search algorithm def binarySearch(nums, target): low = 0 high = len(nums) - 1 while low <= high: mid = low + (high - low) // 2 if nums[mid] < target: low = mid + 1 elif nums[mid] > target: high = mid - 1 else: return mid # key found return low # key not found # Function to find the `k` closest elements to `target` in a sorted integer array `nums` def findKClosestElements(nums, target, k): # find the insertion point using the binary search algorithm i = binarySearch(nums, target) left = i - 1 right = i # run `k` times while k > 0: # compare the elements on both sides of the insertion point `i` # to get the first `k` closest elements if left < 0 or (right < len(nums) and abs(nums[left] - target) > abs(nums[right] - target)): right = right + 1 else: left = left - 1 k = k - 1 # return `k` closest elements return nums[left+1: right] if __name__ == '__main__': nums = [10, 12, 15, 17, 18, 20, 25] target = 16 k = 4 print(findKClosestElements(nums, target, k)) |
Output:
[12, 15, 17, 18]
The above solution to do a binary search to find the insertion point and then tries to find the k closest elements. However, we can combine the whole logic in a single binary search routine. Here’s how the algorithm would look like in C, Java, and Python:
C
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 |
#include <stdio.h> #include <stdlib.h> // Function to find the `k` closest elements to `target` in a sorted integer array `nums` void findKClosestElements(int nums[], int target, int k, int n) { int left = 0; int right = n; while (right - left >= k) { if (abs(nums[left] - target) > abs(nums[right] - target)) { left++; } else { right--; } } // print the `k` closest elements while (left <= right) { printf("%d ", nums[left]); left++; } } int main(void) { int nums[] = { 10, 12, 15, 17, 18, 20, 25 }; int n = sizeof(nums) / sizeof(nums[0]); int target = 16, k = 4; findKClosestElements(nums, target, k, n); return 0; } |
Output:
12 15 17 18
Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 |
import java.util.Arrays; import java.util.List; import java.util.stream.Collectors; class Main { // Function to find the `k` closest elements to `target` in a sorted integer array `nums` public static List<Integer> findKClosestElements(int[] nums, int k, int target) { int left = 0; int right = nums.length - 1; while (right - left >= k) { if (Math.abs(nums[left] - target) > Math.abs(nums[right] - target)) { left++; } else { right--; } } return Arrays.stream(nums, left, right + 1).boxed() .collect(Collectors.toList()); } public static void main(String[] args) { int[] nums = {10, 12, 15, 17, 18, 20, 25 }; int target = 16, k = 4; System.out.println(findKClosestElements(nums, k, target)); } } |
Output:
[12, 15, 17, 18]
Python
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
# Function to find the `k` closest elements to `target` in a sorted integer array `nums` def findKClosestElements(nums, k, target): left = 0 right = len(nums) - 1 while right - left >= k: if abs(nums[left] - target) > abs(nums[right] - target): left = left + 1 else: right = right - 1 return nums[left:left + k] if __name__ == '__main__': nums = [10, 12, 15, 17, 18, 20, 25] target = 16 k = 4 print(findKClosestElements(nums, k, target)) |
Output:
[12, 15, 17, 18]
The time complexity of the above solution is O(n) and doesn’t require any extra space.
Thanks for reading.
To share your code in the comments, please use our online compiler that supports C, C++, Java, Python, JavaScript, C#, PHP, and many more popular programming languages.
Like us? Refer us to your friends and support our growth. Happy coding :)