Solution For 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.

Constraints:
1 <= k <= arr.length
1 <= arr.length <= 10^4
Arr is sorted in ascending order.
-10^4 <= arr[i], x <= 10^4

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:

Approach:
The given array is sorted and the task is to find the k closest elements. We can apply binary search to find the position of the element x and use two-pointer technique to expand the subarray to find the k closest elements. In order to use binary search, we need to find the position of x in the given array. We can use binary search to find the position. Once we know the position of x, we can use two-pointer technique to expand the subarray to find the k closest elements.

Algorithm:

1. Binary search:
   We use binary search to find the index of x in the sorted array. If x is already present in the array, we can directly return the subarray of length k centered around it. Otherwise, we find the index i such that (arr[i] <= x < arr[i+1]).

2. Two-pointer technique:
   We use two pointers, left and right, to expand the subarray of length k centered around x. Initially, left and right point to index i-1 and i respectively. We move left pointer to the left and right pointer to the right until we have k elements in the subarray. The condition for moving the pointers is that if the distance of arr[left] and x is less than or equal to the distance of arr[right] and x, then move left pointer to the left, otherwise move right pointer to the right.

3. Return the subarray:
   Finally, we return the subarray of length k centered around x.

Let’s see the Python code implementation:

class Solution:
def findClosestElements(self, arr: List[int], k: int, x: int) -> List[int]:
# Binary Search to find the index of x in arr
left, right = 0, len(arr) – 1
while left < right:
mid = (left + right) // 2
if arr[mid] < x:
left = mid + 1
else:
right = mid

    # left is the index of x in arr or the index of the element closest to x from the left
    # We expand the subarray in both directions to find the k closest elements
    left_ptr, right_ptr = left - 1, left
    while k > 0:
        if left_ptr < 0:
            right_ptr += 1
        elif right_ptr >= len(arr):
            left_ptr -= 1
        elif x - arr[left_ptr] <= arr[right_ptr] - x:
            left_ptr -= 1
        else:
            right_ptr += 1
        k -= 1

    return arr[left_ptr+1:right_ptr]

Step by Step Implementation For Find K Closest Elements

Given a sorted array, two integers k and x, find the k closest elements 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.

/*

Solution:

We can use a binary search approach to find the index of the element closest to x.

Once we have that, we can use a two pointer approach to find the k closest elements.

We start one pointer at the index of the element closest to x and the other pointer at index+1.

We then keep track of the k closest elements found so far.

We compare the elements pointed to by the two pointers and add the smaller element to our result.

We then move the pointer that points to the smaller element.

We keep doing this until we find k closest elements.

*/

public List findClosestElements(int[] arr, int k, int x) {
    
    // find the index of the element closest to x
    int index = binarySearch(arr, x);
    
    // use two pointer approach to find k closest elements
    int left = index;
    int right = index+1;
    
    // keep track of the k closest elements found so far
    List result = new ArrayList<>();
    
    // add the element at index to the result
    result.add(arr[index]);
    
    // find the k closest elements
    while(result.size() < k) {
        
        // compare the elements pointed to by the two pointers
        // and add the smaller element to the result
        if(left >= 0 && right < arr.length) {
            if(Math.abs(arr[left] - x) <= Math.abs(arr[right] - x)) {
                result.add(arr[left]);
                left--;
            }
            else {
                result.add(arr[right]);
                right++;
            }
        }
        // if we have reached the end of the array,
        // we can just add the remaining elements from the other side
        else if(left >= 0) {
            result.add(arr[left]);
            left--;
        }
        else {
            result.add(arr[right]);
            right++;
        }
    }
    
    // sort the result in ascending order and return
    Collections.sort(result);
    return result;
}

// binary search function
public int binarySearch(int[] arr, int x) {
    int left = 0;
    int right = arr.length - 1;
    
    while(left <= right) {
        int mid = left + (right - left) / 2;
        
        if(arr[mid] == x) {
            return mid;
        }
        else if(arr[mid] < x) {
            left = mid + 1;
        }
        else {
            right = mid - 1;
        }
    }
    
    // if no exact match is found,
    // we return the index of the element closest to x
    return left;
}

def findClosestElements(arr, k, x): 
    
    n = len(arr) 
    
    # if x is present in arr, then find the index 
    # of it 
    if x in arr: 
        index = arr.index(x) 
    else: 
        
        # if x is not present then do binary search 
        # to find the ceiling of x 
        index = bisect.bisect_left(arr, x) 
    
    # print index 
    left = index - 1
    
    # right index 
    right = index + 1
    
    # number of elements to be returned 
    count = k 
    
    # result list 
    result = [] 
    
    # add elements on left of index 
    # to the result 
    while left >= 0 and count > 0: 
        result.append(arr[left]) 
        left -= 1
        count -= 1
    
    # add elements on right of index 
    # to the result 
    while right < n and count > 0: 
        result.append(arr[right]) 
        right += 1
        count -= 1
    
    # sort the result 
    result.sort() 
    
    # return the result 
    return result

var findKClosestElements = function(arr, k, x) {
    // your code here
};

vector findClosestElements(vector& arr, int k, int x) {
    // Initialize a max heap
    priority_queue, vector>, greater>> pq;
    
    // Iterate through the array and push the elements into the max heap
    for(int i = 0; i < arr.size(); i++) {
        pq.push({abs(arr[i] - x), arr[i]});
    }
    
    // Initialize an empty vector to store the k closest elements
    vector res;
    
    // Pop the top k elements from the heap and push them into the vector
    for(int i = 0; i < k; i++) {
        res.push_back(pq.top().second);
        pq.pop();
    }
    
    // Return the vector
    return res;
}

using System; 
using System.Collections.Generic; 
using System.Linq; 

public class Solution {
    public IList FindClosestElements(int[] arr, int k, int x) {
        // create a min heap to store the k closest elements 
        // to x 
        PriorityQueue minHeap = new PriorityQueue(k, 
            new Comparator() { 
                public int Compare(int a, int b) { 
                    if (Math.Abs(a-x) == Math.Abs(b-x)) 
                        return a - b; 
                    return Math.Abs(a-x) - Math.Abs(b-x); 
                } 
            }); 
            
        // go through the array and add elements to the heap 
        // if they are closer to x than the elements currently 
        // in the heap 
        for (int i = 0; i < arr.length; i++) { 
            if (i < k)  
                minHeap.Add(arr[i]); 
            else { 
                if (Math.Abs(arr[i]-x) < Math.Abs(minHeap.Peek()-x)) { 
                    minHeap.Poll(); 
                    minHeap.Add(arr[i]); 
                } 
            } 
        } 
        
        // convert the heap to a list 
        List result = new List(); 
        while (minHeap.size() > 0) 
            result.Add(minHeap.Poll()); 
            
        // sort the list 
        Collections.Sort(result); 
        return result; 
    }
}