Find K-Closest Element

Lecture 60 :- Find K-Closest Element

To find the K closest elements to a given target in a sorted array, we can use a two-pointer approach. The basic idea is to find the position of the target element in the array (or the position where it would be if it's not present) and then expand to the left and right to find the K closest elements.

Here's the C++ code to find the K closest elements to a given target in a sorted array:

cppCopy code

#include <iostream> #include <vector> #include <algorithm> std::vector<int> findKClosestElements(std::vector<int>& arr, int k, int target) {    int left = 0;    int right = arr.size() - 1;    // Find the position of the target (or the position where it would be)    while (left < right) {        int mid = left + (right - left) / 2;        if (arr[mid] < target) {            left = mid + 1;        } else {            right = mid;        }    }    // Initialize the indices for the K closest elements    int start = std::max(0, left - k);    int end = std::min(static_cast<int>(arr.size()) - 1, left + k - 1);    // Use two pointers to expand and get the K closest elements    while (end - start > k - 1) {        if (target - arr[start] <= arr[end] - target) {            end--;        } else {            start++;        }    }    // Copy the K closest elements into the result vector    std::vector<int> result(arr.begin() + start, arr.begin() + end + 1);    return result; } int main() {    std::vector<int> arr = {1, 2, 3, 4, 5};    int k = 3;    int target = 3;    std::vector<int> closestElements = findKClosestElements(arr, k, target);        std::cout << "K closest elements to " << target << ": ";    for (int num : closestElements) {        std::cout << num << " ";    }    std::cout << std::endl;    return 0; }

Example Output:

cssCopy code

K closest elements to 3: 2 3 4

In this code, the findKClosestElements function calculates the K closest elements using a two-pointer approach. The time complexity of this approach is O(log n + k), where n is the size of the input array. The binary search to find the position of the target takes O(log n) time, and expanding to get the K closest elements takes O(k) time.