#1610

Hard

auto_awesomeSliding window with running state updates

LeetCode Problem Workspace

Maximum Number of Visible Points

Determine the maximum number of points visible from a fixed location within a given angle using a sliding window approach.

array math geometry sliding window sorting

Problem Statement

You are given a list of points on a 2D plane, a viewing angle, and a fixed location. Each point and your location are integer coordinates. You cannot move from your location but can rotate to adjust your field of view. Your goal is to determine the maximum number of points visible within the angle from any orientation.

Initially, you face directly east, and rotating counterclockwise changes your viewing direction. The field of view covers angles from [d - angle/2, d + angle/2] for rotation d. Points at your exact location are always visible. Compute the maximum number of points that can be simultaneously observed within this angular window.

Examples

Example 1

Input: points = [[2,1],[2,2],[3,3]], angle = 90, location = [1,1]

Output: 3

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

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

You can only see one of the two points, as shown above.

Constraints

1 <= points.length <= 105
points[i].length == 2
location.length == 2
0 <= angle < 360
0 <= posx, posy, xi, yi <= 100

Solution Approach

Convert coordinates to angles

For each point, compute the angle relative to your location using arctangent. Ignore points at your exact location since they are always visible. This maps the 2D visibility problem into a 1D angular problem suitable for sliding window analysis.

Sort angles and duplicate circle

Sort all angles in ascending order and append each angle plus 360 degrees to handle wraparound. This ensures the sliding window can cover circular ranges without special edge-case handling, maintaining correctness when points span the 0/360 boundary.

Sliding window over sorted angles

Use two pointers to form a window representing the current field of view. Expand the window until the angular difference exceeds the given angle, then move the left pointer forward. Track the maximum window size to find the maximum number of visible points efficiently.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(n log n) due to sorting angles, with n being the number of points. The sliding window runs in linear time O(n) across the extended angle list. Space complexity is O(n) for storing angles, including duplicates to handle wraparound.

What Interviewers Usually Probe

Sorting points by polar angle indicates the candidate is converting 2D coordinates into angular space.
Maintaining a sliding window shows understanding of continuous angular ranges and efficiency.
Handling points at the observer's location separately demonstrates attention to problem edge cases.

Common Pitfalls or Variants

Common pitfalls

Failing to handle points located at the observer's exact coordinates, which are always visible.
Neglecting the circular nature of angles, causing incorrect counts across the 0/360 boundary.
Incorrectly computing angles, such as swapping x and y in arctangent, leading to reversed or shifted windows.

Follow-up variants

Max visible points when the observer can move within a limited grid, combining movement and angle constraints.
Finding visible points from multiple observer locations simultaneously and computing the global maximum.
Computing the minimum angle needed to see a fixed number of points from a stationary location.

FAQ

What pattern does Maximum Number of Visible Points follow?

It follows a sliding window pattern on sorted polar angles, converting 2D visibility into a 1D angular range problem.

How do I handle points at the same location as the observer?

These points are always visible and should be counted separately before applying the sliding window over other points.

Why duplicate angles by adding 360 degrees?

Duplicating angles ensures the sliding window can handle wraparound from 359 to 0 degrees without missing points.

What is the time complexity of the optimal approach?

Sorting angles takes O(n log n) and sliding window passes through them in O(n), so overall O(n log n) time.

Can this method handle very large point arrays?

Yes, the combination of sorting and linear sliding window allows efficient handling of up to 10^5 points within constraints.

terminal

Solution

Solution 1

#### Python3

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

class Solution:
    def visiblePoints(
        self, points: List[List[int]], angle: int, location: List[int]
    ) -> int:
        v = []
        x, y = location
        same = 0
        for xi, yi in points:
            if xi == x and yi == y:
                same += 1
            else:
                v.append(atan2(yi - y, xi - x))
        v.sort()
        n = len(v)
        v += [deg + 2 * pi for deg in v]
        t = angle * pi / 180
        mx = max((bisect_right(v, v[i] + t) - i for i in range(n)), default=0)
        return mx + same

Continue Practicing

#1040 moving stones until consecutive ii #1030 matrix cells in distance order #973 k closest points to origin