Maximum Number Of Visible Points - Leetcode Solution

Problem Statement:

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 vantage point. Let d be the Euclidean distance, in which direction i is pointing at point points[i] = [xi, yi], measured in the X-Y plane. It is guaranteed that 0 <= d <= 1000.

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.

Solution Approach:

Let's break down the problem statement, starting with the field of view. The field of view is essentially an angle that denotes the spread of vision a person has. A normal human being has a field of view between 180 and 200 degrees. In this problem, we've been given the angle, and customarily, we'll represent the direction of vision by a vector pointing towards the right of the positive x-axis.

We will use arctan2() to calculate the angle between the line of sight and the x-axis. arctan2() gives an angle in radians, so we will convert the angle from degrees to radians and subtract pi/2 radians to make the direction vector point towards the right of the positive x-axis. Next, we will sort the points based on their angle with the x-axis, starting from the point directly to our right (i.e., angle with the vector pointing towards the right is zero).

Once we have sorted the points, we can start checking which points are visible, starting with the point to our right and moving clockwise. If a point is visible, we'll add it to our set of visible points and update our direction of sight as the angle subtended by the vector joining our position and the visible point with the x-axis. Finally, we'll return the size of our set of visible points.

To calculate the angle between the two vectors, we will use the formula below:

cos(theta) ≡ A . B / |A| |B|

where A and B are the two vectors, |A| is the magnitude of the vector A, and · represents the dot product operation. The dot product of two vectors A and B is given by:

A . B ≡ Ax * Bx + Ay * By + Az * Bz

where Ax, Ay, and Az are the x, y, and z components of vector A and Bx, By, and Bz are the corresponding components of vector B.

Algorithm:

1. Calculate the angle between each point and the x-axis using arctan2(). Convert the angle from degrees to radians and subtract pi/2 radians to make the direction vector point towards the right of the positive x-axis.

2. Sort the points based on their angle with the x-axis, starting from the point directly to our right (i.e., angle with the vector pointing towards the right is zero).

3. Initialize a set to store the visible points and add the point we are standing on.

4. Initialize the direction of sight as the angle subtended by the vector pointing to the right of the positive x-axis.

5. For each point in the sorted list, calculate the angle between the point and the vector pointing to our position, still on the x-axis.

6. If the angle is less than or equal to the field of view (angle provided in the input), add the point to our set of visible points, and update our direction of sight as the angle subtended by the vector joining our position and the visible point with the x-axis. Continue this process for all points.

7. Return the size of our set of visible points.

Time Complexity: O(N log N)

Space Complexity: O(N)

Detailed Solution:

To solve the problem, we will follow the approach discussed above in the algorithm section.

Code:

class Solution: def visiblePoints(self, points: List[List[int]], angle: int, location: List[int]) -> int: radians = [] x, y = location maxi = 0

    for point in points:
        x1, y1 = point
        if(x1 == x and y1 == y):
            maxi += 1
            continue
        radians.append(math.atan2(y1 - y, x1 - x))
    
    radians.sort()
    
    q = len(radians)
    
    # Double radian list so we always have enough values to make a full 360-degree circle.
    for i in range(q):
        radians.append(radians[i]+ 2 * math.pi)

    ans, i = maxi, 0
    j = 0

    # Iterate i from 0 to the end of the radian list.
    for i in range(q):
        # Keep incrementing j until we cover all the points within view.
        while(radians[j] - radians[i] <= math.radians(angle)):
            j += 1
        ans = max(ans, j - i + maxi)

    return ans

Conclusion:

In this problem, we discussed how to find the maximum number of visible points given a field of view and a set of points on the plane. We used the arctan2() function to calculate the angle for each point, sorted them based on that angle, and then checked which points were visible based on the field of view. We also discussed the mathematical formulas for angle calculations and how to perform dot product operations on two vectors. The time complexity of our solution is O(N log N), where N is the number of points on the plane, and the space complexity is O(N).

1