We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Maximum Number of Visible Points

Number: 1733

Difficulty: Hard

Paid? No

Companies: Nuro, Anduril, Aurora, Nvidia

Problem Description

Given a set of points on the 2D plane, a fixed location, and a viewing angle, determine the maximum number of points that can be seen by rotating your view. Points exactly at your location are always visible. For other points, compute the angle they form relative to the east direction from your location. By using a sliding window over the sorted angles (and handling the wrap-around by duplicating angles with an offset of 360°), determine the maximum count of points that can be covered within any view of the specified angle width.

Key Insights

  • Points at your location are always visible; count them separately.
  • For each point not at the location, compute the angle using atan2 and convert it to degrees.
  • Sort the computed angles.
  • Duplicate the sorted angle array (by adding 360° to each) to seamlessly manage the circular wrap-around.
  • Use a sliding window approach (or binary search) on the sorted array to count the maximum number of points falling within any continuous range of "angle" degrees.
  • The final answer is the sum of the count from the sliding window plus the points at your location.

Space and Time Complexity

Time Complexity: O(n log n) – primarily due to sorting the angles. Space Complexity: O(n) – for storing the computed angles.

Solution

The solution involves the following steps:

  1. Iterate through the given points and separate those that are exactly at the viewing location (always visible) from the others.
  2. For each non-local point, compute the angle (in degrees) with respect to the east direction using the arctan2 function.
  3. Sort the list of computed angles.
  4. Duplicate the angle list by appending each angle plus 360° to handle the circular nature of angles.
  5. Use a sliding window (two pointers) to find the maximum number of points that fit within a window of size "angle" on the duplicated array.
  6. Add the always visible points (those at the location) to the maximum found in the sliding window. This approach efficiently counts the maximum visible points as you rotate your field of view.

Code Solutions

import math

def visiblePoints(points, angle, location):
    loc_x, loc_y = location
    same_position_count = 0
    angles = []
    
    # Calculate angle for each point relative to the location
    for x, y in points:
        if x == loc_x and y == loc_y:
            same_position_count += 1
        else:
            # Calculate the angle in degrees relative to the east direction
            angle_deg = math.degrees(math.atan2(y - loc_y, x - loc_x))
            if angle_deg < 0:
                angle_deg += 360
            angles.append(angle_deg)
    
    # Sort the computed angles
    angles.sort()
    
    # Duplicate the list by adding 360 to each angle to handle the wrap-around
    duplicated_angles = angles + [a + 360 for a in angles]
    
    max_visible = 0
    left = 0
    
    # Use sliding window technique on the duplicated angle array
    for right in range(len(duplicated_angles)):
        # Shrink window until the difference is within the allowed angle
        while duplicated_angles[right] - duplicated_angles[left] > angle:
            left += 1
        max_visible = max(max_visible, right - left + 1)
    
    return max_visible + same_position_count

# Example usage:
points = [[2,1],[2,2],[3,3]]
angle = 90
location = [1,1]
print(visiblePoints(points, angle, location))  # Output: 3
← Back to All Questions