K Readings Nearest a Value
MediumBinary Search
Problem
A sorted array readings holds calibration measurements in non-decreasing order. Given an integer k and a reference value x, return the k readings closest to x, in ascending order.
A reading a is closer than b if |a - x| < |b - x|, or if the distances are equal and a < b.
Example 1
- Input:
- readings = [1, 3, 6, 8, 12], k = 3, x = 7
- Output:
- [3, 6, 8]
6 and 8 are 1 away. Next come 3 (4 away) and 12 (5 away), so 3 wins.
Example 2
- Input:
- readings = [2, 4, 6], k = 2, x = 5
- Output:
- [4, 6]
Example 3
- Input:
- readings = [1, 1, 2, 5], k = 2, x = 0
- Output:
- [1, 1]
Constraints
- 1 ≤ k ≤ readings.length ≤ 10^5
- -10^4 ≤ readings[i], x ≤ 10^4
- readings is sorted in non-decreasing order.
Hint
Show the first hint
The answer is always a contiguous window of length k. What do you need to know to describe it?
Walkthrough
How to approach it
01Clarify before coding
- How are ties broken? The smaller reading wins.
- In what order is the answer returned? Ascending, which a window in a sorted array already is.
- Can x be outside the range of readings? Yes: then the window sits at one end.
02Brute force
Sort all readings by (distance to x, value), take the first k, and sort them back.
Cost: O(n log n) time and O(n) space. Finding the nearest element and expanding two pointers outward is O(log n + k), better but fiddly.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.
This problem is part of Pro.