Find K Closest Elements - Leetcode Solution

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]

1