Find K Closest Elements - Optimised Approach | Leetcode 658 Solution | Searching and Sorting

[debanjanchanda]

Great Explanation. You can however avoid sorting if you just use LinkedList instead and add the items either in beginning or at the end in the while loop (where you choose the next closest element). So if it comes from "r" use addLast() and if it from "l" use addFirst(). And you have now saved step O(k log K) making the whole algorithm run in O(log n) + K time.

[poonamchauhan]

There is a miss in selecting the left and right. What if the mid comes as the first element of the list in that case it would do mid - 1 and receive undefined.
To circumvent that add the following conditional:
[Javascript]
let l
let r
if(mid>=1) {
l = mid-1
r = mid
} else {
l = mid
r = mid+1
}

[shobhitkumar]

Nicely explained. For those who code in c++, there is a stl function upper bound which implements binary search internally. Here is the code for that

vector<int> arr, int k, int x) {
vector<int> ans ;
int ind=upper_bound(arr.begin(), arr.end(), x)-arr.begin() ;
ind-- ;
int i=ind, j=ind+1 ;

while(k--){
if(i<0) ans.push_back(arr[j++]) ;
else if(j>=arr.size()) ans.push_back(arr[i--]) ;
else {
ans.push_back(arr[i--]) ;
else ans.push_back(arr[j++]) ;
}
}
sort(ans.begin(), ans.end()) ;
return ans ;
}

[dojoPojo]

c++. binary search -> expand boundaries -> push it ->don't do sorting at all (If will push in bw sorting required )

first find the lower bound
than expand the range till we hold k numbers within it
if first pointer is having less diff first--
else last++

class Solution {
public:
vector<int> arr, int k, int x) {
int n = arr.size();
int low = 0, high = n - 1;
int idx = n; // Initialize idx to n

while (low <= high) {
int mid = low + (high - low) / 2;
if (arr[mid] >= x) {
idx = mid;
high = mid - 1;
} else {
low = mid + 1;
}
}

int first = idx - 1;
int last = idx;

while (k > 0 && first >= 0 && last < n) {
int diff1 = x - arr[first];
int diff2 = arr[last] - x;
if (diff1 <= diff2) {
first--;
} else {
last++;
}
k--;
}

while (k > 0 && first >= 0) {
first--;
k--;
}

while (k > 0 && last < n) {
last++;
k--;
}

vector<int> ans(arr.begin() + first + 1, arr.begin() + last);
return ans;
}
};

[muditjain]

Good explanation. This code is failing for k = 1,
For eg: [1, 5, 10], k = 1, x = 4
mid = 0;
l = -1;
r = 0;

we add arr[r] in list i.e. 1, but answer should be 5.

Similarly, if we make l = mid and r = mid + 1,
arr= [1, 3], k = 1, x = 2
mid = 1;
l = 1;
r = 2;

we add arr[1] in list i.e. 3 but answer should be 1.
Please help in this problem.

[akatsuki]

One of the best teacher from pepcoding👌just love the way you teach💯

[danishrockz]

for below case it wont give correct ans :

arr > [1, 5, 10]
k > 1
x > 4

above code will print 1 but correct ans is 5..

hence to fix this one we should return low in base case of binary search:



private static int arr, int x) {
// TODO Auto-generated method stub


int low = 0;
int high = arr.length - 1;
int mid = -1;

while(high >= low)
{
mid = ( low + high) / 2;

if( arr[mid] == x)
{
return mid;

}

else if ( arr[mid] > x )
{
high = mid - 1;

}

else
{
low = mid + 1;

}


}

return low;

}

[chirayushetty]

This was too good! The BEST explanation for K closest elements

[azeemali]

Best Solution Ever


class Solution {
public List<Integer> findClosestElements(int[] arr, int k, int x) {
List<Integer> ans = new ArrayList<>();

int lo = 0;
int hi = arr.length-1;

while(hi - lo >= k){
if(Math.abs(arr[lo] - x) > Math.abs(arr[hi] - x)){
lo++;
} else {
hi--;
}
}

for(int i=lo;i<=hi;i++){
ans.add(arr[i]);
}
return ans;
}
}

[nonganbasingha]

Great explanation!!
but instead of adding elements in the answer array on the fly, keep the indices track of lower bound and upper bound. In other words, just compute the range, then iterate in that range to add it in the answer array. In that case, you'll always get a sorted array as the answer.

[jatinbhatoya]

your code fails on this testcase

arr[] =1, 5, 10
k=1 and x=4

[aakashsharma]

Very helpful content😊..thanks to pepcoding team.

[aryandwivedi]

arr = [1, 5, 10], k = 1, x = 5
expected output = [5]
But this code returns [1]

[atharvakulkarni]

Wonderfull Content Keep Uploading Fast !! Thanks a lot!!Wonderfull Explanation

[josephstark]

class Solution {
public:
vector<int> arr, int k, int x)
{
int n=arr.size();
int l=0, h=n-1;
int mid=-1;
int res=0;
while(l<=h)
{
mid=(l+h)/2;

res=mid;
if(arr[mid]==x)
break;
else if(arr[mid]<x)
l=mid+1;
else
h=mid-1;
}
cout<<arr[mid]<<endl;
if(mid>=1)
{
l=res-1;
h=res;
}
else
{
l=res;
h=res+1;
}
vector<int> ans;
while(k>0 && l>=0 && h<n)
{

{
ans.push_back(arr[l]);
l--;
}
else
{
ans.push_back(arr[h]);
h++;
}
k--;
}
while(k>0 && l>=0)
{
ans.push_back(arr[l]);
l--;
k--;
}
while(k>0 && h<n)
{
ans.push_back(arr[h]);
h++;
k--;
}
sort(ans.begin(), ans.end());
return ans;
}
};

[satyamsinha]

Once we sort the elements, time complexity becomes O(klogk) so it is not optimised, it is same as earlier video of brute force optimised to heap approach. Also, please test for test case [1, 1, 1, 10, 10, 10], k = 1, x = 9 on this code.

[Sanjeev.Network]

Your Solution Will Fail for Below Test Cases:-

[1, 5, 10]
1
4

[rosonerri-faithful]

mam ek testcase pass nhi ho hei..leetcode mein...[1, 4, 5] k=1, x=4;
expected answer [5] but [1] aa raha hei

[buu]

consider a case [0, 1, 6, 8, 10] x=4 k=1 the 1st closest element shud be 6(gap2) but according to this we will get 1(gap3) as the ans which is wrong.

[nitunsingh]

Very well explained...Best explanation