Practice/Meta/Leetcode 658. Find K Closest Elements

Leetcode 658. Find K Closest Elements

CodingOptional

Problem

You are given a sorted integer array arr, an integer k, and a target value x. Your task is to find the k integers in the array that are closest to x.

The result should be returned in ascending order. If two integers have the same distance from x, the smaller integer is considered closer.

The answer is guaranteed to be a contiguous subarray of length k from the original array.

Requirements

1. Return exactly k integers from the array
2. The integers must be the ones with the smallest absolute distance to x
3. When two integers have equal distance from x, prefer the smaller integer
4. Return the result in ascending order (which is guaranteed since the input is sorted and the answer is a contiguous subarray)
5. Leverage the fact that the input array is sorted to optimize your solution

Constraints

• 1 ≤ k ≤ arr.length ≤ 10⁴
• arr is sorted in ascending order
• -10⁴ ≤ arr[i], x ≤ 10⁴
• The optimal solution should run in O(log n + k) time where n is the length of the array

Examples

Example 1:

Input: arr = [1, 2, 3, 4, 5], k = 4, x = 3 Output: [1, 2, 3, 4] Explanation: The distances from x=3 are: |1-3|=2, |2-3|=1, |3-3|=0, |4-3|=1, |5-3|=2 The 4 closest are 3 (distance 0), 2 and 4 (distance 1), and 1 (distance 2). Since we need 4 elements and they form a contiguous window, we get [1,2,3,4].

Example 2:

Input: arr = [1, 2, 3, 4, 5], k = 4, x = -1 Output: [1, 2, 3, 4] Explanation: When x is smaller than all elements, the closest k elements are the first k elements.

Example 3:

Input: arr = [1, 3, 5, 7, 9, 11, 13], k = 3, x = 8 Output: [7, 9, 11] Explanation: The three closest values to 8 are 7 (distance 1), 9 (distance 1), and 11 (distance 3). Note that 5 has distance 3 as well, but we prefer [7,9,11] over [5,7,9] because this is a contiguous window problem.