MiddleCodeOccasionalNot answered yet
K elements closest in value to a[index] in a sorted array
Given a non-decreasing array a, an index, and k, return any k elements whose values are closest to a[index].
Requirements:
- O(k) time using two pointers expanding outward from
index. - Handle running off either end and the single-element array.
std::vector<int> findKClosest(const std::vector<int>& a, size_t index, size_t k) {
// your code here
}Write the implementation.
Start two pointers at index-1 and index+1, taking a[index] itself first. Each step compare the left and right candidates' distance to a[index] and take the closer side, until k elements are collected. Guard both ends. O(k) since the array is sorted.
- ✗Running off the left or right end without a bounds check
- ✗Mishandling the single-element array where neither pointer is valid
- ✗Picking the farther of two equally-distant candidates when a tie-break is specified
- →How does this differ from finding the k closest to an arbitrary value x, not a[index]?
- →How would you make the tie-break deterministic toward smaller values?
Contents
Task
Return k elements of the sorted array closest in value to a[index], in O(k).
Solution
std::vector<int> findKClosest(const std::vector<int>& a, size_t index, size_t k) {
std::vector<int> result;
if (a.empty() || k == 0) return result;
long long pivot = a[index];
long long left = static_cast<long long>(index) - 1, right = index + 1;
result.push_back(a[index]);
while (result.size() < k) {
bool takeLeft;
if (left < 0) takeLeft = false;
else if (right >= (long long)a.size()) takeLeft = true;
else takeLeft = std::llabs(pivot - a[left]) <= std::llabs(a[right] - pivot);
if (left < 0 && right >= (long long)a.size()) break;
if (takeLeft) result.push_back(a[left--]);
else result.push_back(a[right++]);
}
return result;
}Key points
- Two pointers expand from
index, taking the closer neighbor. - The sorted order gives O(k): we expand only
ktimes. - Bounds checks on both ends and the single-element array are required.
Contents
