AlgoMaster Sheet – Find K Closest Elements

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| 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,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: Amazon

Solution 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 the k 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