Hard

Quiz

#1453 Maximum Number of Darts Inside of a Circular Dartboard

APPROACH

Alice has thrown n darts at a large wall; darts[i] = [xi, yi] gives the position of the ith dart. Bob wants to position a circular dartboard of radius r on the wall to enclose as many darts as possible (darts on the boundary count).

Given the integer r, return the maximum number of darts that can lie on or inside the dartboard.

Example 1:

Input: darts = [[-2,0],[2,0],[0,2],[0,-2]], r = 2

Output: 4

Explanation: Circle dartboard with center in (0,0) and radius = 2 contain all points.

Example 2:

Input: darts = [[-3,0],[3,0],[2,6],[5,4],[0,9],[7,8]], r = 5

Output: 5

Explanation: Circle dartboard with center in (0,4) and radius = 5 contain all points except the point (7,8).

1 of 4

1:00

What is the optimal approach for this problem?