Leetcode 1453: Maximum Number of Darts Inside of a Circular Dartboard

In this Leetcode problem, we are given a list of point in a 2D-plane, and a radius r. We should find the maximum number of points we can fit in a disk of radius r.

Problem statement

High level algorithm

At the high level, we want to find all the potential “good” centers of the disk, then calculate how many points are in each of them. The approach is simple but a question remains quite difficult, how to find the potential centers?

For each pair of points (a, b) separated by distance d = distance(a, b), one of the three following situations is true:

• d = 2*r, in that case the only disk that contains both these point is the disk with center c = middle[a, b].
• d > 2*r, in that case there is no disk that contains both these points.
• d < 2*r, in that case a lot of disks (infinite number) contain both a and b. We pick both potential centers to be so that a and b are on the border of the disk. We can prove it is optimal, but the idea is essentially that if a and b are not in the border, we are wasting space, and if there is a solution for which only one point is on the border, then we can “jiggle” it a little bit to make 2 points be on the border.