Maximum Number of Visible Points - Solution & Explanation

Problem 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.