658. Find K Closest Elements

Description

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

Constraints

• 1 <= k <= arr.length

• 1 <= arr.length <= 104

• arr is sorted in ascending order.

• -104 <= arr[i], x <= 104

Approach

Links

• Binarysearch

• GeeksforGeeks

• Leetcode

• ProgramCreek

• YouTube

Examples

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]

Solutions

Solution 1

/**
 * Time complexity : 
 * Space complexity : 
 */

class Solution {
    public List<Integer> findClosestElements(int[] arr, int k, int x) {
        if(arr == null || arr.length < k) {
            return List.of();
        }
        int low = 0, high = arr.length-k;
        
        while(low < high) {
            int mid = low + (high-low)/2;
            
            if(x-arr[mid] > arr[mid+k]-x) {
                low = mid + 1;
            } else {
                high = mid;
            }
        }
        
        List<Integer> result = new ArrayList();
        for(int i = low; i < low+k; i++) {
            result.add(arr[i]);
        }
        
        return result;
    }
}

Follow up