How to find the closest pair of points in O(nlogn)? - Inside code

Source code: gist.github.com/syphh/b666869...
🔴 Learn graph theory algorithms: inscod.com/graphalgo
⚙ Learn dynamic programming: inscod.com/dp_course
💡 Learn to solve popular coding interview problems: inscod.com/50problems_course
⌛ Learn time and space complexity analysis: inscod.com/complexity_course
🔁 Learn recursion: inscod.com/recursion_course
NB: This video is ad-free, you can choose to support Inside code by purchasing one of the courses above or dropping a super thanks!
NB2: Discounts of courses above are permanent
I also post content on LinkedIn (inscod.com/linkedin) and Instagram (inscod.com/instagram)

[@insidecode]

Discover the new graph theory algorithms course: inscod.com/graphalgo
🔴
/ \
🔵-🔴
| |
🔴-🔵

[@insidecode]

Fix: At 11:20, the generic form starts with aT(n/b) not aT(n/2)

[@ipranavprashant]

Woah that was some good visualization!

[@stanverlaan1147]

Nicely explained and great animations as well. Good job!

[@insidecode]

Thanks!

[@lonelywife7468]

First video I check of yours. I liked it, it's very informative, keep it up!

[@insidecode]

Thanks a lot! Don't hesitate to watch other ones

[@danieloladele1433]

Wow, Finally a video that explains very well. This is the best so far, even a novice in programming would understand the logic.

[@insidecode]

Wow, thanks!

[@vakman9497]

Speak for yourself I still don’t get it 😂

[@rounakkhuntia1923]

I was not able to understand the rectangle part.

[@leducphuclong]

The best in topic I found, thank you so much !!

[@rodrigomarchi9755]

great video man congrats, keep going!

[@fareswaheed9623]

Man you are incredible in all your videos. This the most interpretive content, i have ever watched ❤💖

[@insidecode]

Thanks a lot for your comment!

[@haritejanarayanabhatla5355]

Hey your algorithms are easily explained and optimal too ..thanks man

[@insidecode]

You're welcome!

[@notonlyit1361]

Just brilliant! Thank you!

[@gautamdangodra4392]

Amazing explanation ! 👏👏

[@ayushmansingh2650]

damn man just amazing explanation of this concept I have never found such a clear explanation for closest pairs among million of points.

[@insidecode]

Thanks a lot

[@uDontSayXx]

Thanks for the clear explanation! Amazing vids :)

[@insidecode]

You're welcome!

[@shahabsalem7272]

Great explanation and the visualisations helped a lot!

[@insidecode]

Thanks!

[@bibeksharma600]

Well explained and the code is very precise and understandable ! Cheers !!!

[@insidecode]

Thankss

[@alfredocossetin5154]

great video, very well explained.

[@Thahira-yc2ys]

Hi, why cant we take d/2 from both side of mid line?

[@tapasranjannayak2366]

may someone please let me know how to made the animation or the tool used for the animantaion.

[@AndyWallWasWeak]

is there a way to modify this to get all pairs starting from the one of the 2 closest points and ending with the pair of the two furthest apart, i.e. get all pairs sorted by distance

[@immortalpuffin6643]

Nice video, keep up the good work!

[@insidecode]

Thanks!

[@milanpatel6240]

I have been asked the same question in Google phone screen. Unfortunately I didn't see your video earlier. Good work.

[@sandeepjnv13]

First of all i want to say that your explanation is of highest standard, almost in the category of 3Blue1Brown.
What i wanted to ask you is do you use python manim lib to animate this?

[@insidecode]

Hello, thanks for the compliment, nope, I use PowerPoint

[@user-ef1uu2yw3y]

Hey,first of all thanks for the amazing explanation!!!
I've 1 question: in 3:46you said that we need to check the points lower than the actual point, why is that? How did we already iterate through the higher points?
Thanks!

[@alperkaya8919]

Because we sorted according to y coordinates. The first point we look is the one which is at top, others are all above. And when you go to second point, it is above of others and below of the first point.

[@arquier]

Thanks, very well explained

[@insidecode]

You're welcome!

[@ghostwar9103]

can some one explain what is the meaning of recursif call the fuction to ger dL dan dR.

[@suhanikalra3532]

thanks for the clear explanation

[@insidecode]

You're welcome!

[@zeyadzakaria5223]

Nice explanation

[@finchshi4342]

Excellent explanation! I just have one question though. When we get the sets of the points , why did we traverse the ysorted array instead of the xsorted array?

[@adiaphoros6842]

Because the band is a vertical strip. Traversing the ysorted traverses the points from top to bottom.

[@sabarivasanvelayutham9256]

Wonderful explanation 👏

[@insidecode]

Thanks!

[@shashwatjohri1503]

i have a feeling the list comprehensions/other things you're wriitng in python will go n^2 anyway

[@ismahanemerzouk2451]

the best explanation ever

[@insidecode]

Thankss

[@akarigale173]

Hi! It seems to me that you did not account the possibility of different points with equal x-coordiantes. It is incorrect to write xsorted_left = xsorted[:n//2], because xsorted[:n//2 + 1] may has the same x-coordiate. And what, for example, should we do if all the points have the same x-coordinate?

[@Ali-qm8ix]

wonderful

[@gabealberro6081]

great vid

[@weirdo9236]

Wonderful

[@user-ig1tf5bx2e]

Just discovered this , channel , neste3ref bik
mor lcovid Insha'Allah ndiro match XD

[@ANGEL_GFREENS]

Could please provide information about the best worst and average cases of this algorithm????

[@hailai1053]

thanks a lot bro

[@insidecode]

You're welcome!

[@user-xn6wo7yi3w]

Nicely explained but i found it tough

[@mohammadyahya78]

Wow!

[@SK-qn5ry]

how to make such animation videos? what skills needed for this??

[@puffvayne5688]

In CLRS textbook, it takes 5 pages to explain this, and I just get confused after reading page 1. Your video is so nice, although your speak speed is a bit quick. With 0.75 speed mode, I get so fxcking clear for this algo. thank you so so much!

[@insidecode]

ohh you're welcome!

[@mrinmoybanik5598]

How to extend this for points in higher dimensions and with other distance metrics like with L-inf ?

[@wizrom3046]

This algorithm only reduces the amount of bruteforcing to HALF of a simple brute force approach. So it doesnt save much time.
I thought up a much faster approach; the killer in computation time is the square root, the whole pythag part really with the mult, mult, sqroot.
So you dont do that.
Instead;
Brute force the lot, BUT just get the distances x1-x2 and y1-y2, the larger of these I call the simple distance. Very quick because it is just two subtractions.
Then the real pythag hypotenuse distance can never be more than 1.41 times the length of the simple distance.
Then keep a live track of the lowest simple distance, and any time a new lowest simple distance is found calc a "limit distance" of 1.5 times the simple distance.
Any future point pair larger than that cannot possibly be the closest pair.
So while the brute force is running; you just compile a short list of any pair where its simple distance is less than the best "limit distance".
I wrote some C code and tested this. 100 random distributed points, means 4950 brute force tests (but they are incredibly fast tests now!) And in the majority of cases there were only 10 to 30 pairs that made it into the final list out of 4950 tests! So that has eliminated 99.5 percent of the pairs!
Even better, you dont have to do the pythag sqroot etc on all 10 to 20 final pairs. Because you already have the smallest simple distance (and the limit distance) you only need to do the pythag testing on 1 to 7 of the final pairs! The average was around TWO pairs needing to be tested!
This algorithm is far quicker than the divide and conquer algorithm in cases where the n (total number of points) is not too large.
As an additional tweak, when brute force testing to get the two subtractions x1-x2 and y1-y2, you can abort the second half of the test (y) if the x simple distance is larger than the limit. You would have to run it in hardware and do time trials to see if that makes a significant difference. Depends a lot on array accessing time.

[@insidecode]

Hello, your solution is interesting if proven right, but it's still in O(n²) time complexity, but the solution presented in the lecture is in O(nlogn), which is way faster for large values of n

[@zholud]

The two points that you found before can be as close to the middle line as they want, thus there is no contradiction in finding them in the rectangle two delta by delta. Second, in your explanation you omitted something re why one looks below some point. You said “let’s look at this point for example” and then out of blue that something has been processed already above it. Finally, Python sucks.

[@insidecode]

Hey I'm interested to discuss your comment point by point. So you're saying that we can find more than 6 points in the two delta by delta rectangle?

[@zholud]

@@insidecode No. I am saying that the contradiction is due to the definition of the minimal distance, not because "it should have been found before" @6:10. Correct logic is "delta prime is smaller than delta, which contradicts that delta is the minimum distance". You lack a bit of structure in your reasoning which makes it hard to follow. You say six but draw 9. Forget to mention that stripe is sorted according to y coordinates and that the algorithm scans down...etc. Sorry. I shouldn't have been rude. Also, it's easy to show that it can't be more than 7 (+1) which would have made the explanation clearer (divide into 8 squares with sides delta/2 there will be two points inside the square => distance less than delta/sqrt(2) < delta => contradiction) - this is easier to explain and doesn't matter too much. It would then suffice to say that it can be shown that you don't need to scan more than 6 (+1).

[@user-kp2uk3cg4g]

Best video