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.
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
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!
@@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.
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]
@@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 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
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! 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 :)
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
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
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.
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.
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 :)
a simpler approach is to sum up the differences of all elements in a window with the target, and if the differences sum of the current window is less or equal to the revious sum we continue sliding and if its strictiy superior then we stop sliding and the result will be the previous window (kinda) (a catch is that if the smallest sum we can get is x then we want the very first window that made this sum not the last because of the definition that lower values are closer than higher values with the sames difference, and so we can use a set(or possibly just a variable to hold the previous sum) to keep track of the sums we saw and a variable to save the left pointer of the first window that had this sum)
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.
// 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
I think the problem would be easier if we would think in terms of midpoint of the values. TS code: function findClosestElements(arr: number[], k: number, x: number): number[] { let [l, r] = [0, arr.length - k]; while (l < r) { let m = r + ((l - r) >> 1); if (x > ((arr[m] + arr[m + k])) >> 1) { l = m + 1; } else { r = m; } } return arr.slice(l, l + k); }
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; }
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.
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.
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
Because the right pointer is always set to len(arr) - k, and m (being the midpoint between left and right) will always be less than right, up until the moment when left == right, at which point the while loop will no longer run.
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; } } }
Here's a good visualization for A[mid], x, and A[mid + k] There are 4 cases: case 1 and 2: // x is closer to A[mid + k], we move window to the right by doing: left = mid + 1; // -------A[mid]------------------x---A[mid + k]---------- // -------A[mid]---------------------A[mid + k]----x------ case 3 and 4: // x is closer to A[mid], we move window to the left by doing: right = mid // -------x----A[mid]-----------------A[mid + k]---------- // -------A[mid]----x-----------------A[mid + k]---------- Either case we don't need to take absolute value because they will all be on the number axis.
![Lp. Сердце Вселенной #60 РОЖДЕНИЕ ЛОЛОЛОШКИ [Финал] • Майнкрафт](http://i.ytimg.com/vi/YoR0pAV9FVQ/mqdefault.jpg)
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
😅
Same with me too . Wondering how I understood all these questions 🙂
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.
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 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
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
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
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
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
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
love it! It's a bit tricky to understand that r = m part, but great explanation though.
The part that he kept saying it is challenging consoled me 🥺🤭 Great Explanation. You got a sub
Omg, thanks for explaining it, i will never understand the solution without thiis awesome illustration!!!
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
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!
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)
@@sentinel-y8l "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)
a simpler approach is to sum up the differences of all elements in a window with the target, and if the differences sum of the current window is less or equal to the revious sum we continue sliding and if its strictiy superior then we stop sliding and the result will be the previous window (kinda) (a catch is that if the smallest sum we can get is x then we want the very first window that made this sum not the last because of the definition that lower values are closer than higher values with the sames difference, and so we can use a set(or possibly just a variable to hold the previous sum) to keep track of the sums we saw and a variable to save the left pointer of the first window that had this sum)
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
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.
@NeetCode i think if we use a little extra space , we can do it in a more understandable way -
result = []
difference = []
for right in range(len(arr)):
diff = abs(x - arr[right])
if len(result) == k:
if difference[0] > diff:
difference.append(diff)
result.append(arr[right])
difference.pop(0)
result.pop(0)
else:
difference.append(diff)
result.append(arr[right])
return result
"This is the way how people from Discuss section figured it out" LOL
What app do you use to sketch? :)
// 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
the solution with the closest value is more intuitive and thanks for the explanation
I think the problem would be easier if we would think in terms of midpoint of the values.
TS code:
function findClosestElements(arr: number[], k: number, x: number): number[] {
let [l, r] = [0, arr.length - k];
while (l < r) {
let m = r + ((l - r) >> 1);
if (x > ((arr[m] + arr[m + k])) >> 1) {
l = m + 1;
} else {
r = m;
}
}
return arr.slice(l, l + k);
}
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)?
Nice explanation of the solution.
What if we use lower bound and then apply two pointers !???
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?
thanks for continuing to make these !
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;
}
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)
@@kxf8608 i don't know wht i can't use Math.abs. i think about this long time. but didn't find out why.... :( poor brain.
i want to know why use target - head & tail - target.
Math.abs wht not work
Great Explanation!
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.
Love it 💓💓
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.
restart everything over again~~ wish me good luck
Good luck Annie! :)
incredible man
Great explanation . thanks
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.
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
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?
Because the right pointer is always set to len(arr) - k, and m (being the midpoint between left and right) will always be less than right, up until the moment when left == right, at which point the while loop will no longer run.
This problem drove me insane. I lost 4500 strands of hair
Outta this world
Can u mention please which project you build for your interview
And please add data structures videos from scratch as well
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
please make the video on Find the Closest Palindrome
i think according to title, i think use heap is more easier.
Can you please post the first solution?
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?
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
k, now find how to center a div
woah!
This is a Hard question!!!!
ahh haa moment
Here's a good visualization for A[mid], x, and A[mid + k]
There are 4 cases:
case 1 and 2:
// x is closer to A[mid + k], we move window to the right by doing: left = mid + 1;
// -------A[mid]------------------x---A[mid + k]----------
// -------A[mid]---------------------A[mid + k]----x------
case 3 and 4:
// x is closer to A[mid], we move window to the left by doing: right = mid
// -------x----A[mid]-----------------A[mid + k]----------
// -------A[mid]----x-----------------A[mid + k]----------
Either case we don't need to take absolute value because they will all be on the number axis.
why is it mid+k not mid+k-1 when it is the right-most number within the window?