Watch 10 video solutions for Maximum Number of Visible Points, a hard level problem involving Array, Math, Geometry. This walkthrough by Happy Coding has 7,048 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
You are given an array points, an integer angle, and your location, where location = [posx, posy] and points[i] = [xi, yi] both denote integral coordinates on the X-Y plane.
Initially, you are facing directly east from your position. You cannot move from your position, but you can rotate. In other words, posx and posy cannot be changed. Your field of view in degrees is represented by angle, determining how wide you can see from any given view direction. Let d be the amount in degrees that you rotate counterclockwise. Then, your field of view is the inclusive range of angles [d - angle/2, d + angle/2].
You can see some set of points if, for each point, the angle formed by the point, your position, and the immediate east direction from your position is in your field of view.
There can be multiple points at one coordinate. There may be points at your location, and you can always see these points regardless of your rotation. Points do not obstruct your vision to other points.
Return the maximum number of points you can see.
Example 1:
Input: points = [[2,1],[2,2],[3,3]], angle = 90, location = [1,1] Output: 3 Explanation: The shaded region represents your field of view. All points can be made visible in your field of view, including [3,3] even though [2,2] is in front and in the same line of sight.
Example 2:
Input: points = [[2,1],[2,2],[3,4],[1,1]], angle = 90, location = [1,1] Output: 4 Explanation: All points can be made visible in your field of view, including the one at your location.
Example 3:
Input: points = [[1,0],[2,1]], angle = 13, location = [1,1] Output: 1 Explanation: You can only see one of the two points, as shown above.
Constraints:
1 <= points.length <= 105points[i].length == 2location.length == 20 <= angle < 3600 <= posx, posy, xi, yi <= 100Problem Overview: You are given a set of 2D points, a viewing angle, and your location. The goal is to determine the maximum number of points you can see if you rotate your field of view. A point is visible if the angle between your viewing direction and the point lies within the allowed viewing angle.
The geometric challenge is that visibility depends on direction rather than distance. Each point can be converted into an angle relative to your location using atan2. Once you represent every point as an angle, the problem becomes finding the largest group of angles that fit inside a window of size angle.
Approach 1: Convert to Angles and Use Sliding Window (Two-Pointer Technique) (Time: O(n log n), Space: O(n))
Compute the polar angle of every point relative to your location using atan2(dy, dx). Points located exactly at your position are always visible, so count them separately. Store the remaining angles in an array and sort them. Because viewing directions wrap around at 360°, duplicate the array by appending each angle plus 2π. Then apply a two‑pointer sliding window to find the largest range where the difference between the right and left angles is within the allowed viewing angle. This converts a circular geometry problem into a linear window scan.
The two pointers expand and shrink the window while maintaining the angular constraint. Each pointer moves at most n times, giving linear scanning after sorting. This technique combines geometry, sorting, and a sliding window pattern.
Approach 2: Angular Sweep (Sort and Range Extension) (Time: O(n log n), Space: O(n))
This method also converts every point into an angle relative to the observer. After sorting the angles, extend the array by adding each value plus 2π to handle circular wrap‑around. Instead of explicitly maintaining two pointers, perform an angular sweep where each angle becomes the start of a viewing interval. Use a moving index to find the furthest angle that stays within start + viewAngle. Track the maximum number of points inside that range.
The angular sweep interpretation frames the problem as selecting the densest interval on a circular number line. The main operations are sorting and expanding the window over the extended array. Conceptually this approach is identical to the sliding window technique but emphasizes the geometry interpretation of sweeping angles.
Recommended for interviews: The angle conversion with a sliding window is the expected solution. It shows that you can translate a geometric visibility constraint into a sorted numeric problem and then apply a two‑pointer window efficiently. Interviewers typically want to see correct angle handling, circular wrap‑around using +2π, and separation of points located exactly at the observer.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Convert to Angles + Sliding Window | O(n log n) | O(n) | General case. Clean two-pointer implementation after sorting angles. |
| Angular Sweep with Range Extension | O(n log n) | O(n) | When reasoning about geometry and circular intervals is clearer. |