Find K Closest Elements - Leetcode 658 - Python

0:00 - Read the problem
1:50 - Drawing Explanation
15:01 - Coding Explanation

leetcode 658

#coding #interview #python
Disclosure: Some of the links above may be affiliate links, from which I may earn a small commission.

[yang]

For those who can't understand ( x - A[mid] > A[mid + k] - x ) think in terms of midpoint of the values ( x > (A[mid + k] + A[mid])/2 )

EDIT: I come back to this comment 7 months after, and I forgot all about this question, or remember posting this comment.

[misso]

Hey NeetCode,

Man, thanks so much for your videos. I just received the news that I'll receive a job offer from Microsoft, and your channel helped me a LOT with the technical interviews.

Thanks so much man!

[subhashreebanik]

Please never stop making videos. I love that you are still making videos despite having a busy schedule.

[VarunMittal-viralmutant]

Just in case someone is looking for O(n) solution:

# Trivial cases
if x <= nums[0]:
return nums[0:k]
elif x >= nums[-1]:
return nums[-k:]

it = iter(nums)
sliding_window = deque(islice(it, k), maxlen=k)

for num in it:
if abs(x-num) < abs(x-sliding_window[0]):
sliding_window.append(num)
return [num for num in sliding_window]

[andrepinto]

The edge cases in this solution are insane... like r needs to len(arr)-k, not len(arr)-1-k but we don't need to check if m+k >= len(arr) because the int div guarantees that m is never = r, x-arr[m] and arr[m+k]-x, can actually be negative, but only one of them at a time, and the logic still holds as the negative number indicates that we should move the window into that direction and actually if you use abs() it doesn't work.

it looks so simple, but it is so fragile. lots of small details that need to be precisely a specific way and not necessarily for obvious reasons.

[numberonep]

Basically a binary search with a fixed sized range instead of a pivot, kinda?...oh boy :d The solution is soooo elegant omg i love it

[ikrenji]

to people confused about why mid = right and not mid = right - 1 ~ try the example a = [1, 2, 3, 4, 5] x = 3 and k = 2. if it was right - 1 in the first step the bounds would end up excluding 3 itself. so in order for the bounds to work out properly it needs to be mid = right

[RM-bgcd]

it's much easier to reason the solution if you think in terms of "arr[mid] + arr[mid + k] < 2 * x", because both extremes of the array are at most going to be 2 * x if every element in the array is equal to x

[vdyb]

Found your channel and love it ! :) Simply awesome and your explanations are so clear. Thank you very much ! Can you find the time to add solutions to these problems ? They seem to be most asked now - 1293 - Shortest Path in a Grid with Obstacles Elimination
1937 - Maximum Number of Points with Cost
1146 - Snapshot Array
2007 - Find Original Array From Doubled Array
2096 - Step-By-Step Directions From a Binary Tree Node to Another

[yunaf]

Great explanation! I have a question, in an interview setting (for FAANG) would the first solution be satisfactory? I imagine there isn't a huge difference between log(n) and log(n-k) so would an interviewer accept the first solution?
Thanks and keep up the great content :)

[shrimpo]

love it! It's a bit tricky to understand that r = m part, but great explanation though.

[CodeSuccessChronicle]

The part that he kept saying it is challenging consoled me 🥺🤭 Great Explanation. You got a sub

[dothuan]

Omg, thanks for explaining it, i will never understand the solution without thiis awesome illustration!!!

[oppo-pxhf]

// for those who cant find simple solution code //brute force approach --> simple O(n)
public static List<Integer> findClosestElements(int[] arr, int k, int x) {

int left = 0, right = arr.length - 1;

// Narrow down the window to size k

//why : right - left :

//The goal is to narrow down the array to exactly k closest elements to x.

// To achieve this, we use two pointers (left and right) and

// adjust them until the size of the window between them is exactly k.


while (right - left >= k) {

int leftDiff = Math.abs(arr[left] - x);

int rightDiff = Math.abs(arr[right] - x);

if (leftDiff > rightDiff) {
left++;
} else {
right--;
}

}

// Collect the elements within the window
List<Integer> result = new ArrayList<>();

for (int i = left; i <= right; i++) {
result.add(arr[i]);
}

return result;

}

[andriyr]

"This is the way how people from Discuss section figured it out" LOL

[vatsalsinha]

I think we could have found the closer of lower_bound and upper_bound and then done the two pointer. The code would have been really small if this works.

[source]

I solved it with a heap that was pretty easy.
I iterated over the array in reverse and added the absolute difference between the i-th element and x (|arr[i] - x|) into the heap.
Note that I added the diff as key and the index i to map back .. i.e. heappush(heap, (abs(arr[i] - x), i))

Then just popped k indices from the heap and returned a sorted ordering of the corresponding k elements.
3 lines of code

[omarllama]

I've actually managed to do it in O(log(n/k) + k).
The reason is that we don't actually need to find the exact location of the idx. We only need to fall in the window of size k, from there we can find the exact window with at most k steps.
To do so, we run the binary search with step size k, which leads to O(log(n/k)).

I can share the code if needed.

[sidazhong]

The l=m+1 and r=m-1 problems were explained vaguely. That made this problem close to hard. I heard another explanation.
Suppose m is 3, k is 2. The window is m to m+k, which is 3 to 5. However, that is 3 nums (3, 4, 5). But k is 2!. It should be 3, 4.
So the window is actually m to m+k-1. the right boundary already - 1. So it is r=m, not r=m-1

[eugbyte]

Does anyone know why the right pointer is simply arr[mid] + k, and not arr[mid] + k - 1? I thought there is a need to offset the index