Maximum Number of Visible Points

Maximum Number of Visible Points

What is this problem about?

The Maximum Number of Visible Points coding problem gives you a list of points (x, y coordinates) and an angle. You are also given your current location (x, y) and a fixed_direction. You can rotate your view up to angle degrees (clockwise or counter-clockwise) from your fixed_direction. You want to find the maximum number of points you can see. Points that are exactly at your location are always visible.

Why is this asked in interviews?

Nuro, Nvidia, Aurora, Amazon, Applied Intuition, Anduril, and Google use this hard problem to test a candidate's understanding of geometry (angles), sorting, and the sliding window technique. It's a classic problem that requires careful handling of angular ranges and circular arrangements.

Algorithmic pattern used

Geometry + Sorting + Sliding Window:

1. Handle Points at Origin: First, count all points that are exactly at your location. These are always visible. Remove them from the points list for further processing.
2. Convert to Angles: For all other points, calculate the angle they make with your location relative to the x-axis. Use atan2(y - loc_y, x - loc_x) to get angles in (-PI, PI] or [0, 2*PI). Convert fixed_direction to radians.
   • atan2(dy, dx) handles all quadrants correctly.
   • Normalize angles to [0, 360) degrees or [0, 2*PI) radians for easier processing.
3. Duplicate for Circularity: After converting all points to angles, sort these angles. To handle the circular nature (e.g., a window spanning from 350 degrees to 10 degrees), duplicate all angles by adding 360 degrees to them. So, [angle1, angle2, ..., angleN] becomes [angle1, ..., angleN, angle1+360, ..., angleN+360].
4. Sliding Window: Now, use a sliding window approach on the sorted and duplicated angle array.
   • For each right pointer, the left pointer should advance such that angles[right] - angles[left] <= angle.
   • The maximum size of this window (number of points) gives the maximum points visible within a single angle sweep.
   • The total visible points will be max_window_size + points_at_origin_count.

Consider the fixed_direction: you can rotate up to angle degrees from your fixed_direction. This means your view window is [fixed_direction - angle/2, fixed_direction + angle/2] (if you can split it evenly) or a window of size angle degrees that can be centered anywhere. The problem statement "rotate your view up to angle degrees" implies you can place a view cone of width angle anywhere. This makes the sliding window approach applicable to the sorted angles.

Example explanation

Location = (0,0), Points = [(1,0), (1,1), (-1,0), (0,1)], Angle = 90 degrees.

1. Points at origin: None.
2. Convert to angles (relative to (0,0), normalized to [0,360)):
   • (1,0): angle = 0 degrees
   • (1,1): angle = 45 degrees
   • (-1,0): angle = 180 degrees
   • (0,1): angle = 90 degrees
3. Sorted angles: [0, 45, 90, 180].
4. Duplicate for circularity: [0, 45, 90, 180, 360, 405, 450, 540].

Sliding Window (window size = 90 degrees):

• [0, 45, 90]: 90 - 0 = 90 <= 90. Count = 3.
• [45, 90]: 90 - 45 = 45 <= 90. Count = 2.
• [90, 180]: 180 - 90 = 90 <= 90. Count = 2.
• [180]: Count = 1.
• [360, 405, 450] (same as [0, 45, 90]): 450 - 360 = 90 <= 90. Count = 3.

Max visible points = 3.

Common mistakes candidates make

• Not handling points at origin: These should be counted separately and then ignored for angular calculations.
• Incorrect angle calculation: atan2 is preferred over atan to correctly handle quadrants. Normalization to a single range (e.g., [0, 360)) is critical.
• Ignoring circularity: A simple sort without duplication won't catch windows that wrap around 0/360 degrees.
• Off-by-one in window logic: Make sure the window size constraint (angles[right] - angles[left] <= angle) is correctly applied.

Interview preparation tip

For the Array Math Sorting Sliding Window Geometry interview pattern, this problem is an excellent test of handling geometric constraints in an algorithmic context. Master angle calculations, normalization, and the sliding window technique for range-based queries on sorted data, especially for circular arrays.