{x}
blog image

Maximum Number of Visible Points

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 <= 105
  • points[i].length == 2
  • location.length == 2
  • 0 <= angle < 360
  • 0 <= posx, posy, xi, yi <= 100

Solution Explanation for Maximum Number of Visible Points

This problem involves calculating the maximum number of points visible within a given angle from a specific location. The solution leverages geometry, sorting, and a sliding window technique.

Core Idea:

  1. Handle Same Points: First, count the points that are located at the same position as the observer (location). These points are always visible, regardless of the angle.

  2. Calculate Angles: For each other point, calculate the angle it makes with the east direction relative to the observer's position. This angle is determined using atan2(y_i - y, x_i - x), which returns the angle in radians.

  3. Sort Angles: Sort the calculated angles. This is crucial for efficiently finding the maximum number of visible points using the sliding window approach.

  4. Extend Angles: Duplicate the sorted angles and add 2 * pi (a full circle) to each duplicated angle. This ensures that we consider points whose angles wrap around from 2π to 0.

  5. Sliding Window: The core of the algorithm lies in the sliding window approach. We iterate through the extended angle list. For each angle, we find the longest consecutive subsequence whose angles fall within the given view angle (angle). The difference between two angles represents the angular distance between them. The window expands until the angular distance exceeds the given view angle. The maximum window size represents the maximum number of points visible at any angle.

  6. Combine Results: Finally, the solution adds the number of points located at the same position as the observer to the maximum window size to obtain the final answer.

Time Complexity Analysis:

  • Calculating Angles: O(N), where N is the number of points.
  • Sorting Angles: O(N log N).
  • Sliding Window: O(N).
  • Overall: The dominant factor is sorting, making the overall time complexity O(N log N).

Space Complexity Analysis:

The space complexity is dominated by the v array which stores the angles. In the worst case, this array can store 2N angles (original angles + duplicates), resulting in O(N) space complexity.

Code Explanation (Python):

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]  # Duplicate and add 2pi for wrap-around
        t = angle * pi / 180            # Convert angle to radians
        mx = max((bisect_right(v, v[i] + t) - i for i in range(n)), default=0) #Sliding window using bisect_right
        return mx + same

The Python code efficiently uses bisect_right for the sliding window to find the count of angles within the view angle in logarithmic time. This optimizes the sliding window part of the algorithm.

Code in other languages follow a similar structure: They perform the same steps: count same points, calculate angles, sort angles, extend the angle list, apply sliding window technique, and finally sum up the results. The differences mainly involve syntax and library usage (e.g., atan2, sorting functions, bisect_right equivalent in other languages).