Think it like this. We want to find center of N points on grid. How to find center of the N points on grid ? ( please find leet code question for the same, I remember solving one question on leet code , Keep in mind , there can be multiple center's of N points )

To find the center sort all the 'x' cordinates, and sort all the 'y' coordinates and then find median of each one of them. Now, from center we can move some points to left, and some points to right. for that I had used binary search, I found few linear solution as well. I couldn't do it in linear time.

One of the steps is similar to Japanese video editorial: if you fix coordinate $$$X_i$$$ you just need to find the interval $$$[Y_l, Y_h]$$$ in which points will not have sum of distances greater than $$$D$$$.

For a fixed $$$X_i$$$ you can find sum of differences of $$$X$$$ coordinates in $$$O(1)$$$ with prefix sums.

Now, all good points will lie in some kind of a "diamond" shape, and as you go over all $$$X$$$ coordinates from left to right this interval $$$[Y_l, Y_h]$$$ will first be increasing, then decreasing (or it could also be empty all the time).

For any coordinate $$$X$$$ the best point is median of $$$Y$$$ coordinates, because it minimizes the difference for all $$$Y_i$$$. At this point you could just binary search both $$$Y_l$$$ and $$$Y_h$$$ up to this median value.

However, since interval $$$[Y_l, Y_h]$$$ is first increasing, then decreasing, you can just do kind of a two-pointer approach, in total you will move both low and high pointers at most $$$3 \cdot (M + D)$$$ times.

Hii, I tried doing this but could not get to this result, Can you please elaborate