Find K Closest Elements

MediumBinary Searchbinary search

Solve this the way you would in the interview: out loud, on a timer, with an AI interviewer asking follow-ups while you code. You get a scored report at the end.

Practice this as a mock interviewFree to start, no account needed

Problem

Given a sorted (non-decreasing) integer array arr, an integer k, and an integer x, return the k elements of arr that are closest to x, listed in ascending order. Element a counts as closer to x than element b when |a - x| < |b - x|, or when the distances are equal and a < b. In other words, ties in distance are broken in favor of the smaller value. If arr contains duplicates, each copy is a separate element and may be picked. x does not need to appear in arr. Target O(log(n - k) + k) time.

Examples

Input: arr = [1,3,5,7,9], k = 2, x = 6
Output: [5,7]
`5` and `7` are both at distance 1 from `6`, and they are the two closest.
Input: arr = [1,3,5,7,9], k = 3, x = 4
Output: [1,3,5]
`3` and `5` are at distance 1. For the third slot, `1` and `7` tie at distance 3, so the smaller value `1` wins.

Constraints

  • 1 <= k <= arr.length <= 10^4
  • `arr` is sorted in non-decreasing order
  • -10^4 <= arr[i], x <= 10^4

What the interviewer grades

A correct solution is one of five scores. The report also grades problem understanding (did you clarify inputs and edge cases before coding), problem solving, communication while you work, code quality, and testing. See a sample report, or read up on the pattern in the lessons.

More binary search problems