1267. Best Square Net
A wildlife camera records animal sightings as map points [x, y] in the array points; the same spot may be recorded several times and every record counts. A ranger throws a square net, with sides parallel to the axes and side length exactly side, onto the map. The net may be placed anywhere, including at fractional coordinates, and a point exactly on the border is caught.
Return the largest number of recorded points that one placement of the net can catch.
Trying every placement is too slow for 500 points with coordinates up to 10^9, but you can sweep over the x coordinate and keep the best y position in a range-add, range-max structure. Aim for O(n log n) time and O(n) space.
Example 1
- Input:
- points = [[0,0],[1,1],[2,2],[5,5]], side = 2
- Output:
- 3
- Explanation:
A net of side 2 placed over [0, 2] by [0, 2] catches the points (0, 0), (1, 1) and (2, 2), the last one on its border, so the answer is 3.
Example 2
- Input:
- points = [[3,3],[3,3],[3,3]], side = 1
- Output:
- 3
- Explanation:
All three records are the same spot, so one net catches all of them and the answer is 3.
Example 3
- Input:
- points = [[0,0],[10,10]], side = 5
- Output:
- 1
- Explanation:
The two points are too far apart for one net of side 5, so the answer is 1.
Constraints
1 ≤ n ≤ 500
0 ≤ x, y ≤ 109
1 ≤ side ≤ 109
Points may repeat.
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
Expected complexity
- Time
- O(n log n)
- Space
- O(n)