Maximum Number of Visible Points
Asked at Anduril
Problem
Maximum Number of Visible Points places you at a location with a field of view of angle degrees that you can rotate freely, and asks for the most points you can see at once. Points at your own location are always visible. Convert each point to a polar angle, sort, and slide a window — remembering that angles wrap around at 360°.
Asked At
| Company | Difficulty | |
|---|---|---|
| Anduril | Hard | View all Anduril questions → |
How to Think About It
Rotation only matters relative to each point's direction, so convert every point to its angle from location using atan2(dy, dx) in degrees.
Points exactly at location have no direction and are visible from any rotation — count them separately and add them at the end.
Key insight: after sorting the angles, the best view is a window [a, a + angle] that starts at some point. Use two pointers to find the largest window with angles[j] - angles[i] <= angle.
Handle wrap-around by appending every angle plus 360 to the sorted list. A window that crosses 0° then appears as a normal contiguous window in the doubled list.
Use a tiny epsilon in the comparison (for example 1e-9) to avoid excluding a point that is exactly on the boundary because of floating-point rounding.
Optimal Approach
Step 1: same = 0, angles = [].
Step 2: For each point: if it equals location, same += 1; else append degrees(atan2(y - ly, x - lx)).
Step 3: Sort angles, then extend with a + 360 for each a.
Step 4: Sliding window: for each j, move i forward while angles[j] - angles[i] > angle + eps; track best = max(best, j - i + 1).
Step 5: Return best + same.
Time: O(n log n). Space: O(n).
What Trips People Up in Real Interviews
Forgetting the wrap-around. A view from 350° to 10° is valid and must be considered.
Including points at the viewer's location in the angle list — atan2(0, 0) gives 0 and would be counted only for some rotations.
Comparing floats without an epsilon, which drops boundary points.
Letting the window grow past the original n points — the doubled list can make j - i + 1 exceed n only if angle >= 360, which the constraints exclude, but mention the cap.
Solution Code
from math import atan2, degrees
def visiblePoints(points, angle, location):
lx, ly = location
same = 0
angles = []
for x, y in points:
if x == lx and y == ly:
same += 1
else:
angles.append(degrees(atan2(y - ly, x - lx)))
angles.sort()
angles += [a + 360 for a in angles]
best = i = 0
for j in range(len(angles)):
while angles[j] - angles[i] > angle + 1e-9:
i += 1
best = max(best, j - i + 1)
return best + sameFrequently Asked Questions
What is the Maximum Number of Visible Points problem?
Maximum Number of Visible Points places you at a location with a field of view of `angle` degrees that you can rotate freely, and asks for the most points you can see at once. Points at your own location are always visible. Convert each point to a polar angle, sort, and slide a window — remembering that angles wrap around at 360°.
How do you solve Maximum Number of Visible Points?
The optimal approach is described in detail above, including step-by-step walkthroughs, complexity analysis, and solution code in Python. Scroll up to the "Optimal Approach" section.
What companies ask Maximum Number of Visible Points?
Maximum Number of Visible Points is asked at Anduril. It is a hard difficulty problem.
What are common mistakes on Maximum Number of Visible Points?
- Forgetting the wrap-around. A view from 350° to 10° is valid and must be considered.
- Including points at the viewer's location in the angle list — `atan2(0, 0)` gives 0 and would be counted only for some rotations.
- Comparing floats without an epsilon, which drops boundary points.
- Letting the window grow past the original `n` points — the doubled list can make `j - i + 1` exceed `n` only if `angle >= 360`, which the constraints exclude, but mention the cap.