Find the K Closest Values in a Sorted Array
Company: LinkedIn
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
Implement `find_k_closest(sorted_values, x, k)` for an ascending array of integers.
Return exactly `k` values that are closest to `x`, also in ascending order. When two values are equally distant from `x`, prefer the smaller value. `k` may be zero and will not exceed the array length.
For example, with `sorted_values = [1, 2, 3, 4, 5]`, `x = 4`, and `k = 4`, return `[2, 3, 4, 5]`.
Aim for `O(log(n - k + 1) + k)` time rather than scanning or sorting the entire array.
```hint Search for a window
Every valid answer is a contiguous window of length `k` in the sorted array, so binary-search the window's left boundary.
```
```hint Compare the values just outside the decision
At a candidate left boundary `mid`, compare how far `sorted_values[mid]` and `sorted_values[mid + k]` are from `x`. On an equal-distance choice, keep the window farther left.
```
### Discussion Extensions
- If the input were unsorted, how would a size-`k` heap change the complexity?
- If the sorted array were too large for memory, how could an index or block layout limit the amount of data read?
Quick Answer: Find exactly k closest values to a target in an ascending integer array, returning them in sorted order. Binary-search the left edge of the answer window, apply the smaller-value tie break, and reach O(log(n-k+1)+k) time.
Implement find_k_closest(sorted_values, x, k). Return exactly k values closest to x from an ascending integer array, and return them in ascending order. If two values are equally distant, prefer the smaller value. The answer must be the deterministic contiguous window implied by that rule.
Constraints
- 0 <= sorted_values.length <= 20.
- sorted_values is in nondecreasing order.
- Every array value and x is an integer from -3,000,000,000 through 3,000,000,000.
- 0 <= k <= sorted_values.length.
- Equal-distance choices prefer the smaller value, and the output remains sorted.
Examples
Input: ([], 0, 0)
Expected Output: []
Explanation: Choosing zero values from an empty array returns an empty list.
Input: ([7], 100, 1)
Expected Output: [7]
Explanation: The only value is selected regardless of the target.
Hints
- The k selected values form a contiguous window in the sorted array.
- Binary-search the window start by comparing sorted_values[mid] with sorted_values[mid + k]; keep the left window on a tie.