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,2,3,4,5], k = 4, x = -1 Output: [1,2,3,4]Solution:
Disclaimer: Don’t jump directly to the solution, try out yourself first.
Practice Questions Find K Closest Elements Company Tags: AmazonSolution 1:
Algorithm:
- Initially let ‘low’ = 0 and ‘high’ = N – 1, Where ‘low’ and ‘high’ tell the range of integers taken in the final answer.
- If at any point (high – low + 1) = K, i.e., the size of the range is ‘K’, that range of integers is the answer. And we create a new array of that range and return it.
- If not, then we check if which one of ‘A[low]’ and ‘A[high]’ is at a smaller distance from ‘X’, whoever is at a smaller distance we keep it, and remove the other.
- If ‘low’ is at a smaller distance, we decrement ‘high’, i.e., high = high – 1.
- If ‘high’ is at a smaller distance, we increment ‘low’, i.e., low = low + 1.
Time Complexity: O(N), where N is the size of the array.
Space Complexity: O(N), since no additional space is used.Where ‘N’ is length of the input array.
#include <iostream> #include <vector> using namespace std; vector<int> findClosestElements(vector<int>& arr, int k, int x) { int low = 0, high = arr.size()- 1; while (high - low + 1 > k) { if (abs(arr[low] - x) <= abs(arr[high] - x)) { high--; } else { low++; } } vector<int> ans; for (int i = low; i <= high; i++) { ans.push_back(arr[i]); } return ans; } int main() { vector<int> input = {10, 12, 15, 17, 18, 20, 25}; int target = 16, k = 4; vector<int> result = findClosestElements(input, k, target); for (int i : result) { cout << i << " "; } return 0; }
Output:12 15 17 18
Solution 2:
We can also find the insertion point
i
using the Binary search Algorithms, which runs in O(log(n)) time. Since finding thek
closest elements takes O(k) time, the overall time complexity of this solution is O(log(n) + k).Time Complexity: O(log(n) + k).
#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> findClosestElements(vector<int>& arr, int k, int x) { // find the insertion point using the binary search algorithm int i = lower_bound(arr.begin(), arr.end(), x) - arr.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 < arr.size() && abs(arr[left] - x) > abs(arr[right] - x))) { right++; } else { left--; } k--; } // return `k` closest elements return vector<int>(arr.begin() + left + 1, arr.begin() + right); } int main() { vector<int> input = {10, 12, 15, 17, 18, 20, 25}; int target = 16, k = 4; vector<int> result = findClosestElements(input, k, target); for (int i : result) { cout << i << " "; } return 0; }Output:
12 15 17 18
This article is contributed by : Sayan Dutta to this article on csforall.in