Find K Closest Elements

90.Find K Closest Elements

Binary Search

Array

Two Pointers

Problem Statement:

Given a sorted 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. If there is a tie, the smaller elements are always preferred.

Algorithm:

1. Use binary search to find the starting index of the k closest elements:
• Set the search range between low = 0 and high = arr.length - k.
• Calculate the middle index, and compare the distances between x and the elements at mid and mid + k.
• Adjust low or high based on the comparison.
2. Once the range is determined, copy the k closest elements starting from low.

Complexity:

Time: O(log(n - k) + k), where n is the length of the array | Space: O(k)

Java Implementation:

public int[] findClosestElements(int[] arr, int k, int x) {
    int low = 0, high = arr.length - k;

    // Binary search for the starting index
    while (low < high) {
        int mid = (low + high) / 2;
        if (x - arr[mid] > arr[mid + k] - x)
            low = mid + 1;
        else
            high = mid;
    }

    // Copy k closest elements to the result
    int[] result = new int[k];
    System.arraycopy(arr, low, result, 0, k);
    return result;
}

Python Implementation:

def findClosestElements(arr, k, x):
    low, high = 0, len(arr) - k

    # Binary search for the starting index
    while low < high:
        mid = (low + high) // 2
        if x - arr[mid] > arr[mid + k] - x:
            low = mid + 1
        else:
            high = mid

    # Return the k closest elements
    return arr[low:low + k]

C++ Implementation:

#include 
using namespace std;

vector findClosestElements(vector& arr, int k, int x) {
    int low = 0, high = arr.size() - k;

    // Binary search for the starting index
    while (low < high) {
        int mid = (low + high) / 2;
        if (x - arr[mid] > arr[mid + k] - x)
            low = mid + 1;
        else
            high = mid;
    }

    // Return the k closest elements
    return vector(arr.begin() + low, arr.begin() + low + k);
}