Find K Closest Elements - Leetcode 658 - Python
Vložit
- čas přidán 27. 07. 2024
- 🚀 neetcode.io/ - A better way to prepare for Coding Interviews
🥷 Discord: / discord
🐦 Twitter: / neetcode1
🐮 Support the channel: / neetcode
⭐ BLIND-75 PLAYLIST: • Two Sum - Leetcode 1 -...
💡 CODING SOLUTIONS: • Coding Interview Solut...
💡 DYNAMIC PROGRAMMING PLAYLIST: • House Robber - Leetco...
🌲 TREE PLAYLIST: • Invert Binary Tree - D...
💡 GRAPH PLAYLIST: • Course Schedule - Grap...
💡 BACKTRACKING PLAYLIST: • Word Search - Backtrac...
💡 LINKED LIST PLAYLIST: • Reverse Linked List - ...
💡 BINARY SEARCH PLAYLIST: • Binary Search
📚 STACK PLAYLIST: • Stack Problems
Python Code: github.com/neetcode-gh/leetco...
Problem Link: leetcode.com/problems/find-k-...
0:00 - Read the problem
1:50 - Drawing Explanation
15:01 - Coding Explanation
leetcode 658
This question was identified as an amazon coding interview question from here: github.com/xizhengszhang/Leet...
#coding #interview #python
Disclosure: Some of the links above may be affiliate links, from which I may earn a small commission. - Věda a technologie
Python Code: github.com/neetcode-gh/leetcode/blob/main/658-Find-K-Closest-Elements.py
link doesnt work
link doesn't work fam
Will it be possible to have a solution using the two pointer approach, for this problem ?
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.
You got it bro!
Oh man indeed. If the target x > midpoint, it is easier to comprehend to shift the L pointer to m+1 position so as to eliminate the left area.
Also, some may confuse by why the position L = m+1 and R = m.
I think in this way:
1. Since m is the temporary left boundary of the window
2. If the outer-range value arr[m+k] is closer to the target x, we should move the window to include the outer-range position and exclude the current left boundary m => which turns out to be m+1 position
(imagine arr[m+k] the outer-range position is the target, so L move to m+1 position would definitely not exclude the target)
3. Else, R = m because we are not sure if m is the target (we only know near to m must be closer), so R should stay including m to search
(imagine arr[m] position is the target, if R = m - 1 would fail)
I am a newbie as well but I hope it helps since I think it is a bit tricky
@@bruceihi tysm for the explanation! im totally dumb and got it only after your comment
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!
what role?
@@karanveersingh5535 Software Engineer. Loving the job :)
@@misso404 best of luck brother. 👍
@@misso404 how did you prepare yourself bro! What questions are asked in interview! Any way to contact you?
@@naveenkumarnalabothu9926 The online assignments were more difficult than the on-site itself. I prepared doing pretty much every exercise on the Codility website, in the order they suggested. For the on-site, I prepared using Leetcode for the most part. I started with the Top 50 list, ordered by acceptance and once I finished those, I solved all problems in the specific list for Microsoft. I finished this 2 or 3 days before the interview, so I recorded videos of me explaining the most popular MS questions to simulate talking with the interviewer.
The on-site had 3 steps, with coding questions, systems design and behavioural. I can't say which questions I got because this would be against my contract.
Please never stop making videos. I love that you are still making videos despite having a busy schedule.
the solution with the closest value is more intuitive and thanks for the explanation
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
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
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 :)
I think most interviewers would accept O(logn) and would prob give hints for better solutions.
There is a solution with O(log(n/k) + k).
i don't think you can ever go wrong with a logn solution in an interview. logn in itself is very efficient
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.
love it! It's a bit tricky to understand that r = m part, but great explanation though.
thanks for continuing to make these !
Just in case someone is looking for O(n) solution:
# Trivial cases
if 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]
just went through itertools in ptyhon after viewing your solution.😂
@@AnnieBox 😄This sliding window recipe is given on that same page, towards the end. I myself am finding itertools to be really useful. Haven't used that module much
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.
Art
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
Thank you for uploading this video. I tried reading the leetcode discuss and didn't fully get it
Could you go through find k pairs with closest sums and kth smallest element in a sorted matrix
What app do you use to sketch? :)
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
Great Explanation!
The part that he kept saying it is challenging consoled me 🥺🤭 Great Explanation. You got a sub
In cases where k is as big as n, O(log n + k) is as good as O(n) only. Considering sorted nature could sliding window be implemented in log(k)?
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
Omg, thanks for explaining it, i will never understand the solution without thiis awesome illustration!!!
Great explanation . thanks
What if we use lower bound and then apply two pointers !???
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
Love it 💓💓
incredible man
I suppose if we do binary search for first closest and then two pointers and k==n, then we'll have O(n) complexity and that's bad.
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
Oh and by the way, initially iterating over the array from the end to the beginning ensures that when we pop the values from the heap, if two values have the same difference (abs(arr[i] - x)), the smaller element will be popped first :)
time complexity matters bro
"I iterated over the array..." -> O(n)
@@andrepinto7895 "I iterated over the array..." -> ...but, if it's with a step
@source144, have you imagined your time complexity? Let me tell you, it is O(kLogN + klogk)
Firstly when I read the problem, I thought that there was some mistake cause it may be too easy. However I realized that I was wrong when try to solve it in 3 hours but did not pass through all of the edge cases.
Dude, how about a goog playlist like goog track in leetcode or most frequent goog questions.
why doesnt the value of arr[m+k] ever go outside the length of arr?
can we use abs(x - arr[m]) > abs(x - arr[m+k]) instead of x - arr[m] >arr[m+k] - x
No. It doesn't work for this testcase:
[1,1,2,2,2,2,2,3,3]
3
3
not working because the key idea here is that the actual search is not about real distances, but about looking for x among A(mid) and A(mid+k)
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.
Please do!
Can you please post the first solution?
please make the video on Find the Closest Palindrome
can any body please explain me why we are taking r=m and not r=m-1
Since we initialize right = arr.Length - k instead of arr.Length - k - 1, we are "commited" to implement the rest of the code to be [left, right).
Thus, explains why while condition has < instead of
"This is the way how people from Discuss section figured it out" LOL
hey neet! can you go over problem 1475. Final Prices With a Special Discount in a Shop
class Solution:
def finalPrices(self, prices: List[int]) -> List[int]:
for i in range(len(prices)):
j=i+1
while(j
restart everything over again~~ wish me good luck
Good luck Annie! :)
Can u mention please which project you build for your interview
And please add data structures videos from scratch as well
Outta this world
// for those who cant find simple solution code //brute force approach --> simple O(n)
public static List 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 result = new ArrayList();
for (int i = left; i
This problem drove me insane. I lost 4500 strands of hair
great solution..but if you are not able to explain this then you are screwed! the interviewer will know that you have mugged it up :p
Better explanation needed from 11:51 to 12:36. I hear "that's how the math works" sometimes, indicating the author is not sure of how the solution works.
Hey man what projects did u put in your resume for Google interview. Do share it.
if you have to ask this question, it means that you are no way prepared to take a faang interview.
Yes I agree that's why I am preparing. Who said that I was prepared?
@@JJ-qv8co what happened now mate no reply? Did I screwed up your plan of trolling strangers in order to look cool?
The easiest way to solve this problem is with 2 pointers, time complexity - O(n), space complexity - O(1)
class Solution:
def findClosestElements(self, arr: List[int], k: int, x: int) -> List[int]:
l = 0
r = len(arr) - 1
while r - l >= k:
if abs(arr[l] - x)
Best C++ Solution 🚀🚀
vector findKCloseElements(vector nums, int k, int x) {
int low = 0, high = k;
int diff = abs(nums[low] - x);
vector res;
while (high < nums.size()) {
// if the diff of right ele. is less or
// ele. at low and high are same, increment pointers
if (nums[low] == nums[high] or abs(nums[high] - x) < diff) {
low++;
high++;
diff = abs(nums[low] - x);
}else {
break;
}
}
for (int i = low; i < high; i++) {
res.push_back(nums[i]);
}
return res;
}
k, now find how to center a div
Why do we need this complicated binary search O(log n) ? I did a simple traversal using queue and it takes similar time.
queue q;
for(int i = 0; i < arr.size(); i++) {
if(arr[i] k) q.pop();
} else {
if(q.size() < k) {
q.push(arr[i]);
} else {
int maxDiff = abs(q.front() - x);
int diff = abs(arr[i] - x);
if(diff < maxDiff) {
q.pop(); q.push(arr[i]);
} else break;
}
}
}
For an array of size 1 Million, your solution would loop 1M times (in its worst case), the binary search would loop 19 times.
Do you see scale ?
O(n) and O(logN) are similar?
woah!
This is a Hard question!!!!
ahh haa moment