YES, correct !!!

thanks dear, thinking of the same how to get rid of extra logn factor by not redefining the way sir did ..

But sir instead of taking 7 points,after visualisation I think only 3 points distance need to be calculated? Where I am going wrong??

@@kirandwivedi7529 yea, you can optimize a bit (to 4 instead of 7), like we don’t need to compute the distance if both points are on the same side, but there is an associated cost to examine if both points are on the same side. Therefore, over all asymptotic complexity won’t change with such optimizations

it is up to us how we want to define T(n). Here, within T(n) = O(n log n), we can solve the original problem + some extra stuffs, which means the complexity of the original problem is also O(n log n).

You will not find a valid pair (i.e., < d) in 1 and 2, because they are on the same side [from the definition of "d"]. But it is possible to have a valid pair in 3 and 4 (because they are on different sides).

Oh, so is the proof of correctness just saying there won't be a point closer to the point than what we find in the third region?

@@emilyhuang2759 proof of correctness says the following, just sort all points within the strip with respect to y-coordinate. Then if there is a pair with distance < d, then the second point within the pair comes as either the first, or second, or third, ...or 7th point after the first point within the pair. So, our algorithm will find it.

If there would have been a point in 1,2 boxes then it would have already been the part of shortest pair in left region and same applies to right region.so that is why we will be able to find shortest pair of points from left and right.

The array in case 3 has all of the points within 2d region. One thing I can't catch up is where the points within 2d x d region come from?

Suppose "p" is the current point and "q" is the other point (which is super close and underneath p) and (p,q) is the closest pair. You are right, this pair wont be captured while doing our procedure at "p", but it will be captured when we do our procedure at "q''.

@@algorithmsbysharmathankach7521 we take a look at next 7 points right and not the ones that are already scanned

@@algorithmsbysharmathankach7521 the points are sorted by y co ordinate and we check with next 7 points not previous ones

"d" is the minimum of d1 and d1, i.e., the shortest distance between all possible pairs, where both points are completely on either the left side or the right side. Now this little boxes are completely within the LEFT or RIGHT side. Note that d/root(2) is the length of the diagonal. Now if there are two points within a square, the distance between them will be at most d/root(2), which is shorter than "d", which contradicts the definition of "d" at the first place.

@@algorithmsbysharmathankach7521 So, if I understand correctly, at first we declared that minimum distance of the two points is d and d/root(2) is less than d thats why 2 points cannot be in the same square boxes. Right? Thank you so much:))

@@timeinabottle9155 The min distance of 2 points that are completely within one side (left or right), which is computed via recursion.

Sure, we can modify the algorithm a bit and reduce the number of distance computations per point to 4 from 7, although the asymptotic complexity remains the same.

Yes, we can fix a point (on a side) and just compare it with 4 (instead of 7) points on the other side. But these 4 points can be anyone's among the next 7 points (if we sort with respect to Y). So, we might still need to examine the next 7 points. The answer is yes, we can do a bit of optimization here, but the asymptotic time will be the same.

Since we are dividing and conquering in the same way as merge-sort, we just interleaved our algorithm with mergesort, so that the sorted list (at every level of merging) comes without extra cost.

watch from 17:30 to 20:00