Find K Closest Elements
Explore how to identify the k closest numbers to a target value within a sorted array using modified binary search. Understand the criteria for closeness and how to handle ties by selecting smaller values. Practice implementing this efficient search approach to improve problem-solving skills in coding interviews.
We'll cover the following...
Statement
You are given a sorted array of integers, nums, and two integers, target and k. Your task is to return k number of integers that are close to the target value, target. The integers in the output array should be in a sorted order.
An integer, nums[i], is considered to be closer to target, as compared to nums[j] when |nums[i] - target| |nums[j] - target|. However, when |nums[i] - target| |nums[j] - target|, the smaller of the two values is selected.
Constraints:
-
knums.length -
nums.length numsis sorted in ascending order.-
nums[i],target
Examples
Understand the problem
Let’s take a moment to make sure you've correctly understood the problem. The quiz below helps you check if you're solving the correct problem:
Find K Closest Elements
What are the k closest integers to target if the following data is given as input?
nums = [1, 3, 5, 7, 9, 11]
k = 4
target = -7
[1, 3, 5]
[1, 3, 5, 7]
[1, 3, 5, 9]
[0, 1, 3, 5, 7, 9, 11]
Figure it out!
We have a game for you to play. Rearrange the logical building blocks to develop a clearer understanding of how to solve this problem.
Try it yourself
Implement your solution in main.cpp in the following coding playground. We've provided a useful code template in the other file that you may build on to solve this problem.
#include <iostream>#include <vector>#include "BinarySearch.cpp"std::vector<int> FindClosestElements(std::vector<int> nums, int k, int target){// Replace this placeholder return statement with your codereturn {};}