Katkat
Back

Find the K Closest Values in a Sorted Array

LinkedInSoftware Engineer · Onsite
MediumSoftware EngineerOnsiteCoding & Algorithms

Last updated

This problem tests binary search and window optimization to find the k nearest elements to a target in a sorted integer array.

Problem Statement

Given a sorted array of integers arr, a target integer target, and an integer k, return the k closest integers to target in the array. The result must be returned in sorted order.

An integer a is closer to target than an integer b if `|a - target| list[int]:


### Constraints
- `1 <= k <= len(arr)`
- `1 <= len(arr) <= 10^4`
- `arr` is sorted in ascending order.
- Values in `arr` and `target` are within the range `[-10^4, 10^4]`.

### Examples

**Example 1:**
Input: `arr = [1, 2, 3, 4, 5]`, `k = 4`, `target = 3`
Output: `[1, 2, 3, 4]`
Explanation: 3 is already in the array, the surrounding elements are chosen.

**Example 2:**
Input: `arr = [1, 10, 15, 25]`, `k = 2`, `target = 20`
Output: `[15, 25]`
Explanation: `|15-20| = 5`, `|25-20| = 5`. Both are equidistant, the sorted output is `[15, 25]`.

### Edge Cases
- `k` equals the length of the array.
- `target` is smaller than the first element or larger than the last element of the array.

Hints

Hint 1

Instead of searching for elements, try to find the starting index of the window of size k.

Hint 2

Binary search over the possible starting indices in the range [0, n - k].

Hint 3

Compare the distance of the element at the current window start with the element just outside the right end of the window to decide which direction to move.

Follow-up questions

  • What is the time complexity of your solution, and can you explain how it is faster than a linear O(n) scan?
  • How would you modify your approach if the input array were not sorted?
  • If the array contained duplicates, would your logic for handling tie-breaks change?