1610. Maximum Number of Visible Points
Asked at Anduril
Difficulty
Hard
Time
O(n log n)
Space
O(n)
Pattern
Array
Companies
1
Problem
You stand at a fixed point location = [posx, posy] on a 2D plane. You start facing east, but you may rotate to any direction. Your field of view is angle degrees wide, and it is centered on the direction you face. So if you rotate counterclockwise by d degrees, you can see every direction in the range [d - angle/2, d + angle/2].
You are given a list of points, where points[i] = [xi, yi]. A point is visible if the angle between it and your facing direction falls inside your field of view. Return the maximum number of points you can see with one rotation.
Two special rules matter. First, points that sit exactly at your location have no direction, so they are always visible no matter how you rotate. Second, points do not block each other — even if two points lie on the same line of sight, you see both.
A rotatable wedge of width angle
Constraints
- ●
1 <= points.length <= 10^5 - ●
points[i].length == 2 - ●
location.length == 2 - ●
0 <= angle < 360 - ●
0 <= posx, posy, xi, yi <= 100
Examples
points = [[2,1],[2,2],[3,3]], angle = 90, location = [1,1]3points = [[2,1],[2,2],[3,4],[1,1]], angle = 90, location = [1,1]4points = [[1,0],[2,1]], angle = 13, location = [1,1]1Asked At
1 companies| 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).
Angles, sort, then slide a window
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
O(n log n) timefrom 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 runs in O(n log n) time and O(n) space. Scroll up to "Optimal Approach" for the step-by-step walkthrough, diagrams, and code in Python, C++ and Java.
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.