Closest Pair of Points (Divide and Conquer) Explained

[@softsun2134]

probably the clearest explanation I've seen of this algorithm thanks!

[@andy0401ify]

OMG there hasn't been any explanation better than yours ever!!!! couldn't be any clearer!!!!! Thank you so much!!!

[@Chellali.A]

Thank you so much , I wanted to bring to your attention a concern I have regarding the time complexity of the closestPair function in this algorithm. Specifically, when calling the function for all elements of Y in the following lines: dl = closestPair(X[1 .. mid], Y); dr = closestPair(X[mid+1 ... n], Y); I believe this approach increases the time complexity. The search for the strip is performed in Y, which has a length of N. Consequently, the work done by subproblems becomes O(N), where N is the number of all the points of the problem. This happens because Y is not getting smaller through the dividing process. I propose a modification where the work by subproblems is O(L), where L is the length of the subproblem. To achieve this, the Y in the call to closestPair(X, Y) should contain the same elements as X, with X being the array that undergoes division. Thank you for considering this suggestion.

[@pm_ranj]

That was the nicest video of this algorithm on YT so far, keep it up

[@berouminum3424]

Truly an on "point" explanation. Thank you, keep going!

[@SewonKimMusic]

this is amazing. Thank you so much for saving our souls in algorithm class.

[@sahilverma286]

You have explained the topic very effectively and you made everything easy. Before I had plenty of doubts but now you made it clear. Keep on posting such videos. I'll be eagerly waiting for your next videos ^_^

[@ANGEL_GFREENS]

What are best average and worst time complexity of this algorithm called closest pair by divide and conquer

[@balakr231]

The only tutorial on the channel had to be the on the topic i was looking for.

[@deadscammer3374]

Thank you after 3 years

[@finiteimpulse3765]

Clear and precise explanation with a lovely voice.

[@soumitramondal4013]

The way you explained is really awesome. Can we expect more videos like this?

[@vinamrasangal8436]

no bc

[@aishwaryaramesh4877]

Wow, amazing video! You explained it so well that I finally understood it after breaking my head for sooo many days. Thanks a ton! 🙏🙏

[@gezhi9420]

讲得太好了，非常清晰。Visualization is awesome.

[@MagicThanos7]

we definitely need more of these explanations from you

[@rafsanishazidnasif5291]

Thank you so much. Couldn't be more clear

[@tanvirtanvir6435]

3:35 2-delta distance 4:08 2d*d O(1) for each point

[@FAUSTINEWANG-k7v]

This is such a great explanation! Thank you so much.

[@nopesep9123]

Incredible explanation, the best I have found, thank you very much!!!!!!!!!!!!!!!!!!!!!!!!!

[@taivinh1986]

the best explanations I've ever seen

[@JR-vc4gm]

Wow great video! I had a hard time to understand why there was a maximum number of point in the delta region. Thank you

[@mohammadyahya78]

amazing amazing amazing and the best explanation for this problem. Thank you

[@VikashKumar-tr9cq]

Code in c++ : #include #include using namespace std; bool compare(paira , pairb) { return a.second=e)return LONG_MAX; if(e-s+1==2) { long d = dis(x[e],x[s] ) ; return d ; } int mid = (s+e)/2 ; long l = fun(x, s, mid) ; long r = fun(x,mid+1 , e ) ; long d = min(l,r) ; vector arr ; for(int i =s ; i= x[mid].first-d and x[i].first n; pair* arr = new pair[n]; for(int i = 0; i < n; ++i) { cin >> arr[i].first >> arr[i].second; } cout

[@peterthegreat8464]

Beautiful algorithm explained by a beautiful voice

[@AntonKimS]

Fantastic video! Best explanation I have seen so far. Would be awesome to see more videos on other algorithms. Thank you!

[@albertswiecicki395]

Quality content, I was looking for. Thank you!

[@lujainabdulrahman9572]

Thank you so much, best explanation I’ve come across!

[@VultureGamerPL]

Simple and to the point. Nicely done.

[@HaziqAzlanShah]

hello, i wish you could do more explanation videos like this. I really appreciate your clear explanation!!!

[@kirby0918]

Great explanation, thank you! But I think the time complexity of pseudo code provided isn't obviously O(n log n) due to the step of selecting S from whole Y. Since you pass the whole Y in each call, the "n" isn't split into halves when recursion, but n -> 2n -> 4n -> ... where n is the length of X. I think it could be done in O(n) by merging the Y-sorted sub-arrays from divided problems.

[@skarasavvidis]

yes, this is correct. The recursive calls must be made with 2 modified Ys. One for the left points and one for the right. Or, as you suggest, by merging the points. To merge them, you would need to return not only d, but also the points merged by y coordinate

[@JoeBaloney]

5:57 Why for j=1 to 7? what's the 7 about?

[@sohammitra8657]

An excellent explanation of the problem

[@xiaochenliang]

your video is very very great! I love it. Thank you very much!

[@la337erf]

This is amazing. Please make more videos on other algorithms!!

[@bayanassali2339]

Very visual and clear explanation thank you so much!

[@juswanth.t133]

Great one, especially the 2δ X δ part!!

[@Zinab8850]

Amazing explanation 🤩🤩 the animation was extremely helpful in seeing how the algorithm works

[@waynej_xyz]

so great , that was i am loving version.

[@itsmayankkr]

Thank you so much for such a nice explanation :))

[@ansharora3248]

+1 @Mayank Kumar

[@mohitmridul6164]

+1 ansh arora

[@rituparnaw]

@@mohitmridul6164 +1

[@rituparnaw]

@Mayank Kumar +1

[@ankitrao8313]

Ha bhaiya. It helped a lot . Maza aa gaya 🤗🤗

[@danieloladele1433]

Excellent work and very easy to understand

[@seharpanesar5132]

This is so good. Thank you!!

[@ngchongpeng]

i have a question. does the question assume there are coincident points? if coincident points arent allowed, then when checking in the 2d * d rectangle, can we just check for the next 5 points instead of 7? since coincident points will not happen. thanks.

[@alvjkd]

wow this was amazing. thank you so much for this!!

[@samanasghari6213]

That was awesome Keep it going🎉🎉

[@samoyed_fps]

It's really a clear explaination, amazing !

[@leilu5607]

This is an amazing explanation! 讲得好棒！

[@gsmdfaheem]

This was perfect.....Thank you so much!

[@DanielLochner]

Fantastic presentation! Thanks a bunch! :)

[@kenz7788]

the best explanation ever

[@terensahin]

that was a great explanation, thank you

[@ayushmishra2731]

Should the space complexity not be O(n)? Explaination below. It's true that for each call with make take O(n) space which is the n for that call. And the depth is log n. However, in each next call N is also half. So it's like N + N/2 + N/4 .... 1, which is 2n, so O(n) When we are in a recusrive call, we shouldn't consider space from calls that have finished. And for a given call only it's previous sizes are active. It's similar to how in merge sort (with using extra auxilary array to merge), the space complexity would still be O(n).

[@manrajsingh4644]

Cleanest explanation ❤️

[@Corgamos]

Thank you, very nicely explained!

[@dhyeyparekh4994]

very very nice explanantion....

[@1arpaxad]

I think it's enough to iterate j from 1 to 4 because in each side the maximum number of points is 4

[@squidsword0]

amazing work. helped me a lot

[@onurbaran4016]

For split pairs why we iterating 1 to 7?

[@Pure_117]

4:40 bookmark

[@guolongli5524]

Thank you! Great explanation!

[@MahdeeMushfiqueKamal]

Peeps who are here for BUET-18's offline-8 comment here

[@nahianshabab724]

hey bro 🙂

[@asifhaiderelhan]

kere mama mmk

[@mdtokitahmid2970]

Hola🥲

[@CodeNCode-rm8ci]

Yo....bro

[@osamahaque]

hehe

[@AkashKumar-jl3sw]

Amazing thank you for your explanation !!!!

[@Japo0po0]

Best explanation, bar none

[@1516TanviDeshpande]

Ommggg amazing explaination

[@Gintoki.Sakata918]

Please make more videos🥲 If possible please create a whole series of your lectures.

[@storiesshubham4145]

Great explanation mam.

[@soyei]

great explanation, thank you

[@shubhbhalla3850]

Great explanation !

[@ghostwar9103]

how did you find delta in 6,8 do you brute force the left and the right with out divide it ?

[@AgeOfNerds]

thank you! Very well explained!

[@l501l501l]

Pretty clear. Thank you.

[@potzko2552]

this is such a good and clear explanation, do you mind if I use it for teaching?

[@jonathanguzman8584]

God Bless you, you are great

[@Muntasir007]

Thank you so much ❤❤

[@Zaznobable]

thanks a lot for your explanation

[@Adityarm.08]

8:00 Y sorted points also need to be halved before recursion to ensure optimal complexity, right? This can be done via (id) based filtering of Y into Y_left & Y_right based on a HashSet representation of what goes into X_left & X_right. Am I missing something? Great explanation otherwise :)

[@alihsanelmas]

Well explained!

[@azmainfaiak8111]

3:55 7 points explanation

[@saketkumar4972]

how did she arrived at the 2nd strip

[@KaranDoshicool]

best explanation

[@filz4461]

Can you do more videos, please?

[@advaitanand2524]

Can we expect some more videos?

[@hashirkz]

tysm it makes so much more sense now lol

[@鐘振元-i8o]

講的很好！😊

[@LalithaManasviniS.P]

Thank You ma'am.

[@MoreCRNonYT]

Thank you! :D

[@alanye7542]

Thank you!

[@darshanbhaiya8711]

Great Explanation but i have not understood clearly

[@MMM-hn8os]

wonder how this video ' made

[@udaykiran1390]

First of all i was on a thought she will definitely waste my time but u nailed it 🔥

[@joelwillis2043]

now find the optimal solution for N-dimensional Euclidean space.

[@wizrom3046]

Who told you the brute force solution was n squared? Once a test has been performed, it can be tagged as done. Then that pair test does not need to be done again. Consider 4 points; 1,2 3,4 1 needs to test 2,3,4 2 only needs to test 3,4 (because 1,2 test is already done)) 3 only needs to test 4 That is only 6 tests need to be performed, not 16 (n squared) Formula is probably factorial n... Please get gour facts right!

[@iDeer70]

Consider 5 points, 100 points, 10000 points, and let me know if you still think the formula is factorial n (hint: sum of arithmetic sequence). Then please get your fact right about Big O Notation! Keep in mind that constants are dropped when calculating time complexity.

[@marceloenciso6665]

In that case the running time would be something like n(n-1) + (n-1)(n-2) + ... + (n-k+1)(n-k) = (n^2-n) + (n^2-3n+2) + (n^2+(1-2k)n+(k^2-k)) = kn^2 + a. Where a is the sum of other lower power terms. Since big O notation drops those lower terms and constants we get that big o notation is n^2.

[@wizrom3046]

@@marceloenciso6665 agreed, sorry its not factorial, the formula for total number of tests is; (n squared -n) /2 So the total number of tests will always be less than HALF of n squared Anyway this divide and conquer method it still a poor way of solving the problem. Doing all those square roots is a real mess. This is how I would do it for least amount of CPU cycles; 1. Brute force all points but only testing points AFTER the point. (N squared -n) /2 tests; 1a. Get the x dist and y dist (very fast, just 2 subtractions needed) 1b. keep the larger of the two, very fast (we will call this the simple distance) 1c. Put the simple distance in a list, ordered by size (very fast) TRICK; The actual distance can never be more than the simple distance *1.41 so only need to test those list entries that are LESS then the smallest entry *1.41 Now we are only needeing to do the mults and sq roots on a tiny percentage of the point pairs; 2. Process down the ranked list; 2a. Do the pythag mult mult sq root etc to get real dist 2b. If less than prev best, save that as best 2c. If the list entry is >top entry *1.41 then job is done! Ive been coding high perf algorithms for 30 years and mostly had to do it on low perf 8bit systems with no math processor etc. The algorithm I outlined above is just my first attempt but would be far quicker than the divide and conquer system provided that n is not excessively large.

[@wizrom3046]

Ok, i just wrote some quick c code to test my algorithm. n = 100 points, randomly distributed x and y values using; random(1024) Brute force ranked point distances by my "simple distance" ie the largest of x1-x2 or y1-y2 (4950 tests) Then ONLY needed to do the pythag mult sqroot etc on ANY points where; simple dist

[@dontplsgx7934]

@@wizrom3046 You should really learn about big O notation before saying anything. (n squared - n) / 2 -> (n^2) /2 - n/2 -> n^2*1/2 - n*1/2 When we calculate big O notation, we only care about the *dominant terms* and we do not care about the coefficients. Thus we take the n squared as our final big O (in this case n^2 is the dominant term and you can eliminate all the other parts in the big O notation).

[@rezachitsaz4923]

thanks. useful.

[@ammaralmarzooq5764]

الله يدخلش الجنة يارب

[@varaprasad10]

thank you

[@vatg2001]

Thanks

[@spiridiant]

感恩

[@averagestanduser6967]

W vid

[@ZihanLiu-vq2lt]

牛逼 上课没听懂在你这里听懂了