The only reason they mention that constraint is because they don't want you to count a single pair twice. Notice that we calculate the absolute difference of the pairs. Thus, the ordering is irrelevant.
@@NeetCodeIO Gotcha, didn't realize that part. Irrespective of the ordering, a pair will be counted if the absolute difference matches the condition. Thanks!
At first, I carefully watched your intuition explanation, had to replay few parts at times to understand properly, then when I understood what approach you talked about, I tried to code it myself. I did it. But the complexity looked pretty bad, still I was happy I did it. And then I watched you writing the code and saw that in the helper function, I wrote a longer while() loop than you because I used while() for the whole window movement instead of just l, so when i changed that part in my code, the complexity got so much better. Anyway, my point is.. THANK YOU SO MUCH FOR ALWAYS GUIDING ME! I don't watch the code right away unless it's about graph or trees because I am weak at those but you always help with the intuition part if I had been stuck for quite some time. Thanks a lot.
no, you guys are wrong. Assuming you store all the differences between all the pairs (O(n^2) space compexity), you can run QuickSelect in linear time to get the Brute Force T.C to n^2
Btw could you please explain, how to know if the value of mid in the binary search, actually exists as a difference of 2 elements in the array? We just assume there are set of differences from 0 to max but we may not have these?
The only thing I'm confused about is what is the guarantee that m will be in the differences array. Not necessary that all values in [0, max] will be a possible difference of any pair. Eg. [1,1,6] has [0,6] possible difference values but only 0 & 5 actually exist.
M doesn't have to be in the differences array, we can still count differences that are less than or equal to m. Eventually our m will be a valid difference.
@@NeetCodeIO How do we prove that m will be eventually valid? The thing I was doing wrong was that in the while loop when pairs == k, i was returning m and I'm not able to quite understand how not exiting early prevents this.
@@siddharth-gandhi idk if this makes sense but if we have 3 as a valid solution for the example, we will end up reducing the search space, then when we do binary search we will find any values smaller than 3 that also satisfy having greater than or equal to k num of pairs that are less than it, as we keep reducing the search space we’ll get to a point where we get an invalid value we’re searching on, it’s kind of difficult to see in ur example but if we have [1,2,6] as the arr and [1,4,5] as the pair dists, we can set our search space as [0, max - min] -> [0, 5] and k = 1, then our first mid value we search is 5 - 0 // 2 = 2 and we see that there is >= 1 pair of at least dist 2, so now high = 2, low remains 0, and mid = 2 // 2 = 1, now when we count pairs on 1 (which is in the array) it will give us the same result as the higher value from before, so we can be sure the dist is in the array because we r looking for the smallest value for mid that satisfies k
@@siddharth-gandhi I had the same question. It turns out that if you have an array such as [1,1,2,2,3] with k=4, and you started the binary search with the range [0,6] since 6 is the max element, the differences array would be [0,1,1,2,1,1,2,0,1,1] which sorts to [0,0,1,1,1,1,1,1,2,2]. Then we can clearly see the kth smallest sum is 1 at index 3 of the differences array (0-indexed). Now using the algorithm, we would start with r = 6 and l = 0 and get m = 3 with pairs = 10. We would then get r = 3 and l = 0 which would give us a new m = 1 for which pairs = 8. We would then get r = 1 and l = 0 which would give us a new m = 0 for which pairs = 2, leaving us with a final l = r = 1. In the above approach, m eventually becomes valid because the binary search keeps choosing the smallest valid number such that helper(m) is at least equal to k. In the example, the smallest m that achieves this is m = 1 where we have pairs = 8 because if we go to m = 0 we have pairs = 2 which is less than k. This suggests that since m = 0 only had 2 pairs, there must be 6 differences that are equal to 1 in the original array, therefore making m = 1 have pairs = 8. There is no other integer between m = 0 and m = 1 that would cause the pairs to go from 2 to 8, so it is as if incrementing the potential sum (which is m) by 1 adds 6 pairs. Therefore m = 1 regardless of the situation must correspond to some valid difference in the original array because of the jump in 6 pairs. The binary search always find the smallest m such that it is on this cusp.
If you can implement it you are on really good road. There was a leetcode daily challenge that had similar solution and I didn't think of the solution, I felt like I couldn't figure it out myself, but I remembered the previous problem so I was able to solve this
I kinda like this question because it just combines multiple basics to solve it, not like some others solved with a crazy complicated specific algorithm.
TYSM, I struggled with understanding the binary search approach and 16:22 is literally an "Aha" moment. After that it still took sometimes for me to come up with how to count the pairs but it still much better than twiddling my thumbs trying to understand the editorial of leetcode
The brute force time complexity will be of order O(n^2 . logn) since there will be n * (n -1) / 2 distance pairs, and sorting them would have time complexity O(m . logm) where m = n * (n -1) / 2, which make it O(n^2 . logn).
i was thinking instead of using sliding window on every binary search, why dont we use dynamic programming and store the number of pairs with 0 difference, 1 diff , 2 diff etc. .... that way we dont have to use 2 pointer every time .
This one is remind me of problem 4. Median of 2 sorted array I think this is almost impossible to solve it in the first time unless u have a really good base in mathematic :D
I guess I might've missed it, but how do we know that the solution will be between 0 and the max element in the array? I'm not understanding the max element portion.
like if input array was [0,100,200] I get that the max possible diff is 200. However how does m relate to that. oh I see! I think the `diff` value we are comparing the two pointer diffs to is nums[m], not the index value itself. So in the first round here, m=1, nums[m] = 100. So we do the two pointer approach to get all diffs
oh finally! For anyone else confused about this, l and r are NOT index values. They are values in the range 0 -> max(nums). Therefore, in my example above, the first value of `m` would be 100, NOT 1 (if it were a index based binary search).
Great explanation . ❤ I tried brute force first but failed as 17/19 test cases passed. Again i optimised the space to O(max) then the code got submitted but still the time and space complexity is huge. Tried and tried... but i wasn't able to optimise. I thought of taking hints from this solution. First hint: Binary Search.... No idea to move further . Second hint: Finding the no. of pairs which are less than X in O(n) average time complexity. Still confused. Third Hint : Applying two pointers to count. After third hint i got the solution and understood the solution.
why we take max(nums) except len(nums) - 1? Sry for mb silly quiestion, but i can't understand : ( And one more, if we take max(nums) we can get Error index out of range, coz max num can be like 10^6 and max length of massive can be 10^5 for example, am I wrong?? Pls help me to understand!
It feels like we are coding for some low memory 80s device where every space counts. Its 2024 memory is cheap, why do we even care about space complexity.
it's supposed to test how well you can actually think. Leetcode isn't supposed to be practical it's supposed to test how good of a problem solver you are.
why are the problems so hard lately, we're not even halfway through the month...
Did you solved this one on ur first try or looked up to the hints?
For me BS wasn't intuitive at all.
better for your business lol
this exact question was asked in interview for entry level job 😢
@@Currmygold69 which company ?
@@Currmygold69 really? what company?
halfway through the video i forgot what the question was
Yeap, my 45 days streak ends here
use a ticket buddy
What is mean by ticket and how it will help us. Can anyone explain
@@sagayaraj6298 you can regain your streak by spending 70 points
Don't worry the problem isn't even that hard.
The problem :
I thought you won't drop the video, thank you Neetcode
The question states that we want pairs nums[i] and nums[j] where 0
us bro us
It seems Leetcode also forgot about the condition. Neetcode's solution passed all test cases.
@NeetCodeIO Can you explain what's going on here? There is clearly something that I'm missing.
The only reason they mention that constraint is because they don't want you to count a single pair twice.
Notice that we calculate the absolute difference of the pairs. Thus, the ordering is irrelevant.
@@NeetCodeIO Gotcha, didn't realize that part. Irrespective of the ordering, a pair will be counted if the absolute difference matches the condition. Thanks!
This problem was really difficult for me lmao. It took 2-3 replays just to visualize what's going on. Thanks for the explanation!
At 20:09 there are 10 pairs with difference
At first time tried to implement myself. Make combinations of pairs and their differences put in an array. 17 / 19 passed
us bro, brute force did really passed 17 testcases and then boom :(
If you really wanted it, then you wouldve done
If num == (testcase): return (testcase answer)
At first, I carefully watched your intuition explanation, had to replay few parts at times to understand properly, then when I understood what approach you talked about, I tried to code it myself. I did it. But the complexity looked pretty bad, still I was happy I did it. And then I watched you writing the code and saw that in the helper function, I wrote a longer while() loop than you because I used while() for the whole window movement instead of just l, so when i changed that part in my code, the complexity got so much better. Anyway, my point is.. THANK YOU SO MUCH FOR ALWAYS GUIDING ME! I don't watch the code right away unless it's about graph or trees because I am weak at those but you always help with the intuition part if I had been stuck for quite some time. Thanks a lot.
Actually brute force T.C is n^2logn since there are n * (n-1) /2 pairs
yup yup, it's O(n^2 * log(n^2)) = O(n ^ 2 * (2 * log(n))) = O(n^2 logn)
no, you guys are wrong. Assuming you store all the differences between all the pairs (O(n^2) space compexity), you can run QuickSelect in linear time to get the Brute Force T.C to n^2
@@sarmohanty fair enough, didn't think that deep coz brute force was instantly out of the question
Btw could you please explain, how to know if the value of mid in the binary search, actually exists as a difference of 2 elements in the array? We just assume there are set of differences from 0 to max but we may not have these?
The only thing I'm confused about is what is the guarantee that m will be in the differences array. Not necessary that all values in [0, max] will be a possible difference of any pair. Eg. [1,1,6] has [0,6] possible difference values but only 0 & 5 actually exist.
M doesn't have to be in the differences array, we can still count differences that are less than or equal to m. Eventually our m will be a valid difference.
@@NeetCodeIO How do we prove that m will be eventually valid? The thing I was doing wrong was that in the while loop when pairs == k, i was returning m and I'm not able to quite understand how not exiting early prevents this.
@@NeetCodeIO So like in [1,1,6], with k = 1 differences are [0,5,5] and l,r = 0,6. First m is 3 and thus pairs = 1 (since only 0 is
@@siddharth-gandhi idk if this makes sense but if we have 3 as a valid solution for the example, we will end up reducing the search space, then when we do binary search we will find any values smaller than 3 that also satisfy having greater than or equal to k num of pairs that are less than it, as we keep reducing the search space we’ll get to a point where we get an invalid value we’re searching on, it’s kind of difficult to see in ur example but if we have [1,2,6] as the arr and [1,4,5] as the pair dists, we can set our search space as [0, max - min] -> [0, 5] and k = 1, then our first mid value we search is 5 - 0 // 2 = 2 and we see that there is >= 1 pair of at least dist 2, so now high = 2, low remains 0, and mid = 2 // 2 = 1, now when we count pairs on 1 (which is in the array) it will give us the same result as the higher value from before, so we can be sure the dist is in the array because we r looking for the smallest value for mid that satisfies k
@@siddharth-gandhi I had the same question. It turns out that if you have an array such as [1,1,2,2,3] with k=4, and you started the binary search with the range [0,6] since 6 is the max element, the differences array would be [0,1,1,2,1,1,2,0,1,1] which sorts to [0,0,1,1,1,1,1,1,2,2]. Then we can clearly see the kth smallest sum is 1 at index 3 of the differences array (0-indexed). Now using the algorithm, we would start with r = 6 and l = 0 and get m = 3 with pairs = 10. We would then get r = 3 and l = 0 which would give us a new m = 1 for which pairs = 8. We would then get r = 1 and l = 0 which would give us a new m = 0 for which pairs = 2, leaving us with a final l = r = 1. In the above approach, m eventually becomes valid because the binary search keeps choosing the smallest valid number such that helper(m) is at least equal to k. In the example, the smallest m that achieves this is m = 1 where we have pairs = 8 because if we go to m = 0 we have pairs = 2 which is less than k. This suggests that since m = 0 only had 2 pairs, there must be 6 differences that are equal to 1 in the original array, therefore making m = 1 have pairs = 8. There is no other integer between m = 0 and m = 1 that would cause the pairs to go from 2 to 8, so it is as if incrementing the potential sum (which is m) by 1 adds 6 pairs. Therefore m = 1 regardless of the situation must correspond to some valid difference in the original array because of the jump in 6 pairs. The binary search always find the smallest m such that it is on this cusp.
I am able to implement once understanding the method. But how on earth do I come up with this solution...
If you can implement it you are on really good road. There was a leetcode daily challenge that had similar solution and I didn't think of the solution, I felt like I couldn't figure it out myself, but I remembered the previous problem so I was able to solve this
I kinda like this question because it just combines multiple basics to solve it, not like some others solved with a crazy complicated specific algorithm.
Thank you very much for that explanation, I was really struggling with figuring out how to get around the O(n^2) problem with the pairs.
TYSM, I struggled with understanding the binary search approach and 16:22 is literally an "Aha" moment.
After that it still took sometimes for me to come up with how to count the pairs but it still much better than twiddling my thumbs trying to understand the editorial of leetcode
this is too hard yaar,not able to understand even with your explaination
Thank you so much Sir..!
Had to watch twice to finally get it. Thanks for making these videos🙂
Where does it state that the numbers are positive? I didn't see it in the problem statement you showed. Same for the limits on num[i].
I did an easy brute force and it passes 18/19 cases
Great explanation, thank you
Well explained. Thank you !
Do you have to continue counting the number of pairs with differences
why are we setting r to m instead of m - 1? why don't we just do the while l
This becomes more interesting if we need to find the kth distinct smallest diff
The brute force time complexity will be of order O(n^2 . logn) since there will be n * (n -1) / 2 distance pairs, and sorting them would have time complexity O(m . logm) where m = n * (n -1) / 2, which make it O(n^2 . logn).
Biro ur a godammm genius !!!!!!!!!!!!!
wont the search space be 0 to nums[n-1]-nums[0] when nums is sorted?
Got asked this problem while applying as a server for a restaurant
I got the intuition and coded it myself using c++ . Well my question is how am I supposed to come to this approach myself?
can do r=nums[-1] as it is already sorted , improves runtime
i was thinking instead of using sliding window on every binary search, why dont we use dynamic programming and store the number of pairs with 0 difference, 1 diff , 2 diff etc. .... that way we dont have to use 2 pointer every time .
this one is a career crusher
How the hell i will came up with this idea with that much efficiency within 20 minute timespan
tried heap solution but still got a TLE 18/19
Neetcode = The G.O.A.T
This one is remind me of problem 4. Median of 2 sorted array
I think this is almost impossible to solve it in the first time unless u have a really good base in mathematic :D
Damn thats crazy
I guess I might've missed it, but how do we know that the solution will be between 0 and the max element in the array?
I'm not understanding the max element portion.
Since we calculator absolute values, none of the pair differences can be outside that range
@@NeetCodeIO Ahh. Okay that makes sense!
counting sort worked for cpp
why is m considered a potential difference? Don't differences rely on the values themselves, not index values?
like if input array was [0,100,200] I get that the max possible diff is 200. However how does m relate to that.
oh I see! I think the `diff` value we are comparing the two pointer diffs to is nums[m], not the index value itself.
So in the first round here, m=1, nums[m] = 100. So we do the two pointer approach to get all diffs
oh finally! For anyone else confused about this, l and r are NOT index values. They are values in the range 0 -> max(nums). Therefore, in my example above, the first value of `m` would be 100, NOT 1 (if it were a index based binary search).
Can anyone explain how the sliding window is O(n). Because the inner while loop also get executed a lot ... is it not significant..?
Looks more like magic to me😆😆
Great explanation . ❤
I tried brute force first but failed as 17/19 test cases passed. Again i optimised the space to O(max) then the code got submitted but still the time and space complexity is huge. Tried and tried... but i wasn't able to optimise. I thought of taking hints from this solution.
First hint: Binary Search.... No idea to move further .
Second hint: Finding the no. of pairs which are less than X in O(n) average time complexity. Still confused.
Third Hint : Applying two pointers to count.
After third hint i got the solution and understood the solution.
The Code :
The Intuition and thought process:💀
thanks a lot :')
almost coded my self
Damn you must be very simple if you were able to code yourself.
@@zweitekonto9654 means?
i thought it would let me get away with a brute force heap
why we take max(nums) except len(nums) - 1? Sry for mb silly quiestion, but i can't understand : (
And one more, if we take max(nums) we can get Error index out of range, coz max num can be like 10^6 and max length of massive can be 10^5 for example, am I wrong??
Pls help me to understand!
mind bending
Gyatt, awesome explanation for such a tricky problem
question: how do you get your search range if you don’t get all pairs 😢
this is a pretty hard question
Me at the start : ooh! This looks simple, why is it in hard level
Me at the end of video : I need to have RTX 4090 to process this information 😢
my brain gived error but thank you so much for solution
Another EGO CRUSHER! xD
the first time neetcode won’t work for me
It feels like we are coding for some low memory 80s device where every space counts. Its 2024 memory is cheap, why do we even care about space complexity.
it's supposed to test how well you can actually think. Leetcode isn't supposed to be practical it's supposed to test how good of a problem solver you are.
its scary difficult
17/19 brute force gang
25 mins, im cooked
Let's go sleep ma broder
I thought my heap solution is good enough with the time complexity of O(k·log(n)), sadly still TLE.
:(((
BRO I came in 40 seconds, 0 views.
damn your gf must be impressed 😜
@@NeetCodeIO 🤣🤣🤣
freakcode
@@NeetCodeIO is cooking! :D
bro climaxes in O(1)
Your while loop won't even execute.
why is that
NeetCode