Return the k values in a sorted array closest to a target, with smaller-value ties
Company: Microsoft
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Other
You are given a list `arr` sorted in non-decreasing order, an integer `k`, and a target value `x`. Return the `k` elements of `arr` that are closest to `x`, listed in ascending order.
### Function Signature
```python
def k_closest_elements(arr: List[int], k: int, x: int) -> List[int]:
```
### Rules
- Element `a` is closer to `x` than element `b` when `|a - x| < |b - x|`, or when `|a - x| == |b - x|` and `a < b`.
- Every position in `arr` is a separate element, so a value that appears several times can be chosen several times.
- `x` does not have to appear in `arr`, and it may lie below the smallest or above the largest element.
- The returned list is sorted in ascending order and may contain repeated values when `arr` does.
### Constraints
- `1 <= k <= len(arr) <= 10^4`
- `arr` is sorted in non-decreasing order
- `-10^4 <= arr[i] <= 10^4`
- `-10^4 <= x <= 10^4`
### Examples
Example 1
```text
Input: arr = [1, 3, 5, 8, 12], k = 3, x = 6
Output: [3, 5, 8]
```
The distances to 6 are 5, 3, 1, 2 and 6; the three smallest belong to 5, 8 and 3.
Example 2
```text
Input: arr = [2, 4, 6, 8], k = 3, x = 5
Output: [2, 4, 6]
```
4 and 6 are both at distance 1. 2 and 8 tie at distance 3, and the smaller value, 2, is closer by the tie rule.
Example 3
```text
Input: arr = [1, 1, 2, 2, 2, 5], k = 4, x = 2
Output: [1, 2, 2, 2]
```
The three 2s are at distance 0; the fourth element is one of the two 1s at distance 1.
Overview: Given a sorted integer list, a count k and a target value, return the k elements closest to the target in ascending order. The problem tests a precise tie rule that favors smaller values, duplicate values, targets outside the array's range, and working efficiently on already sorted input.
Read the full Microsoft Software Engineer interview experience this question came from