Closest Readings to a Target
EasyHeap / Priority QueueFree
Problem
A thermostat calibration tool has an unsorted list of temperature values and a reference temperature target. Pick the k values closest to target (by absolute difference). When two values are equally close, the smaller value is considered closer.
Return the k chosen values sorted in ascending order.
Example 1
- Input:
- values = [3, 9, 14, 6, 11], target = 10, k = 3
- Output:
- [6, 9, 11]
Distances: 3→7, 9→1, 14→4, 6→4, 11→1. The three closest are 9 and 11 (distance 1), then 6 beats 14 at distance 4 because it is smaller.
Example 2
- Input:
- values = [1, 2, 3, 4, 5], target = 3, k = 2
- Output:
- [2, 3]
3 is at distance 0; 2 and 4 tie at distance 1 and the smaller one, 2, wins.
Constraints
- 1 ≤ k ≤ values.length ≤ 10^5
- -10^4 ≤ values[i], target ≤ 10^4
- values is not sorted and may contain duplicates.
Hint
Show the first hint
Define a single 'closeness key' for each value so that ties are already resolved by the key.
Walkthrough
How to approach it
01Clarify before coding
- How are ties in distance broken? The smaller value wins.
- In what order is the result returned? Ascending by value, not by distance.
- Is the input sorted? No; with a sorted input, binary search plus two pointers would be better.
02Brute force
Sort all values by the key (|v - target|, v), take the first k, and sort them by value.
Cost: O(n log n) time and O(n) space. Correct, but it orders all n values when only the k best matter.
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.