God will understand

I'd like to think of the step 6 as follows: Consider a d by d square fully contained in the right strip. Then there can be at most four points in the square, i.e., the four points all lying on the four vertices of the square, since if there are five points or more, then there will be at least one pair of points whose distance is smaller than d, which is a contradiction. This holds similarly for the left strip as well. Now, let P be any point in the strip of width 2d centered at the vertical line shown in the video. For any 2d by 2d square containing P and fully contained in the strip, there exists at most eight points. In this worst case, P is at the center of the 2d by 2d square, and the other eight points lie on vertices and the middle of all edges. Thus, it takes only constant time to verify whether there is a point on the other side of P whose distance from P is smaller than d. The number of points in strip is O(n), and each point takes a constant to verify. So, verifying whether there is a pair of points lying on different sides whose distance is smaller than d takes O(n).

I got lost after 4th minute. The most important part is unintelligible.

sound quality should be improved

At least explain the code properly.

I get confused on 7 points because actually none of the points on your side will be the result because they are all > d. so you only compare to the other 4 points on the other side which is not enough if you try to draw a circle with a radius of d center at your point. It touches more "square" on the other side if you are close to the strip. I think this is very clear to everyone.

My right ear enjoyed it xD

Thanks for your great video. Quick question: According to "Algorithm Design" by Tardos the time complexity is O(nlogn) I didn't get how you derived it to be to O(n(logn)^2). I guess we can't use master theorem in the way you formulated it as the theorem uses big theta and this case we had big O.

You can turn on the subtitle

T(n) = 2T(n/2) + O(n) + O(n) + O(n) T(n) = 2T(n/2) + O(n) T(n) = T(nLogn)

I absolutely love the sound quality , Its just fukin amazing !

I think you guys should try to implment 1D closet pair which is easier to understand. The basic idea behind these is Devide and Conquer. We understand the idea is the most important. public static int mindist(int[] a, int lo, int hi) { if (lo >= hi) { return Integer.MAX_VALUE; } else if (lo == hi - 1) { return a[hi] - a[lo]; } else { int m = lo + (hi - lo) / 2; int delta_1 = mindist(a, lo, m); // left points set int delta_2 = mindist(a, m + 1, hi); // right points set int delta_3 = a[m + 1] - a[m]; // strip points min distance return _Math.min(delta_1, delta_2, delta_3); } }

Isn't the comparison done for all the points in the strip in stripClosest function rather than just looking at only 7 points? What am I missing?

Why do i need to compare to other 7 points? Isn't it enough to compare to at most the 4 points that are on the other side of the strip? I mean, if the 2 points that yield the minimum distance are at the same side of the strip, i would have found them before making the strip, when comparing all the points at each side... so i only need to compare a point on the left side with the 4 points of the right side that are at most at d distance, or am i missing something?

what if the points are (-3,-4), (-2,4),(-2,-2) for example? wouldn't this be stuck as strip contains the 3 points then you'd solve them recursively only to be stuck again with the same 3 when u check around midpoint

Awesome Harshit , started to see some complex problems being taken care by geeks for geeks team now . kudos , I break my head to understand the strip ( how to calculate only required points not all of them in strip, couple of years ago ) this lucid explanation definitely deserves more likes . first from me :) . Keep doing good work . - Sunny

Let's say the data set is immense, with over 10^9 values of points. Would it be wise to split the list into 3 instead of 2 and do it accordingly? If so, why can't I split it into 3 parts for smaller data sets as well or even split into 4 or 5?

the time complexity here isn't optimal. it assumes you're sorting by the y for each recursive call, which is unecessary. you only need to do it once at the start, which makes the recurrence T(n) = 2T(n/2) + O(n) = O(nlogn)

Very useful contents.thank u👍

*Wonderful code, God bless! As my Indian friends say: "Hats off, sir!"*

02:38 step number three, confuse me? why 12 and 14 are the closest ones, or 15 and 3 are the closest ones for each side, how we calculate it?

thanks for creating these videos

Those who didn't get the above explanation, This video might help- kzfaq.info/get/bejne/rs9diqlhnNilgas.html (from 20:00)

if you are wondering how can there be a finite number of points (8) from which we need to compute distances, here's an explanation in simplest words. I've had way too much free time during this quarantine. Here's the explanation of what you wanted with proof. Once you've found out the LD(minimum distance on the left side of the separator line L) and RD(...........right side of..........), you'd find delta which is the minimum of the aforementioned distances(DELTA=min(LD,RD)). Now, its time for finding the distance b/w the points lying on the EITHER SIDE of the line L. So you'd now construct the strip (of length 2*Delta) across L and search for the points lying within the strip and distanced < DELTA. We will now build a square(assume its either on the left or right side of the line L just for simplicity) with side=DELTA and see how many points fit in it conforming to our requirement that minD

my right ear enjoyed this.

in the stripClosest() method, the most outer for, shouldn't it be for( int i = 0; i < size - 1; i++) ? because when i = size - 1, J = i + 1 which is equals to size, strip[J] would result an error wouldn't it? please tell me if i'm missing something

how did you find dl and dr in step 3? and what time complexity did it take?

I could not understand why 7 points comparison only. How did you use the rectangle geometry also unknown? Request you to stress more on the 7n comparison part as it's not clear. Why you say d/square-root(2) should not be possible. I believe it is less than d and hence minimum. I need more lucid videos on this topic.

code doesnt seem to compile for C++

Combine sounds please

Great video! Pan the sound to the center tho pls

what about farthest pair of point???

Where you use |pq| formula

thankyou. pretty clear explanation

yes guys I am sitting to your right

How we can arrange the elements on the plane?

will that points diagram will be given?

DnC solves it in O(n logn) The code is horrible

well this is calculating distance between two closest points, not the points themselves. be specific. disappointed

Although your channel and videos are great, you have to work hard on your English or at least speak much slower. Or at super-least, add the textual transcription of the text you say. It's very hard to understand the speech now unfortunately. Otherwise you're doing a great teaching work, keep on!

i see all these comments saying that very good explanation but i don't think this explanation is good at all my personal opinion.

My left ear: 😐😐

amazing

Sound in only one ear. Fix It.

HER HER HER OMG -_- -_-

I did not understand your English accent. It was wired

can u please be louder or else use mic please

If this problem is an interview problem, I'll be damned

Evlo try panalum ninga solratha purinjika mudila😑😑😑😑

Supari nikal K baat kr re baba

Please, reduce your accent, it's unreal to understand some words clearly. i can't watch video properly!

Why is this taught by a telephone scammer?

This guy is cooked, doesn't even make sense in the optimization part...

Come ooon! I can't understand what this guy is talking about, his speech is bad! AAAAAAAAAAAAA!

Horrible accent. Half of the video is unintelligible