Katkat
Back

Return the k values in a sorted array closest to a target, with smaller-value ties

MicrosoftSoftware Engineer · Other
MediumSoftware EngineerOtherCoding & Algorithms

Last updated

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.

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

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

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

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

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.