Find K Closest Elements

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

Test Cases

Example 1:

Example 2:

Constraints:

• 1 <= k <= arr.length

• 1 <= arr.length <= 10<sup>4</sup>

• arr is sorted in ascending order.

• -10<sup>4</sup> <= arr[i], x <= 10<sup>4</sup>

Solution

Java Python

class Solution {
    public List<Integer> findClosestElements(int[] arr, int k, int x) {
        int l = 0, r = arr.length - 1;
        while(r - l >= k) {
            if (Math.abs(arr[l] - x) > Math.abs(arr[r] - x)) {
                l++;
            } else {
                r--;
            }
        }
        List<Integer> result = new ArrayList<>();
        for(int i=l; i<=r; i++) {
            result.add(arr[i]);
        }
        return result;
    }
}

class Solution:
    def findClosestElements(self, arr: List[int], k: int, x: int) -> List[int]:
        left, right = 0, len(arr)-1
        while right - left  >= k:
            if abs(x - arr[left]) > abs(arr[right] - x):
                left += 1
            else:
                right -= 1
        return arr[left: right+1]