LeetCode 1610: Maximum Number of Visible Points
Problem Description
Explanation:
- To solve this problem, we need to calculate the angle between each point and our location.
- We can calculate the angle using the arctan2 function, which returns the angle in radians between the x-axis and the point.
- After calculating the angles, we can sort them and consider the range of angles starting from each angle and ending in angle + 360 degrees.
- We can then iterate over the points and calculate the maximum number of visible points for each range of angles.
- Finally, we return the maximum number of visible points.
Time Complexity: O(n log n) where n is the number of points. Space Complexity: O(n) for storing the angles.
:
Solutions
import java.util.*;
class Solution {
public int visiblePoints(List<List<Integer>> points, int angle, List<Integer> location) {
List<Double> angles = new ArrayList<>();
int sameLocation = 0;
for (List<Integer> point : points) {
if (point.get(0) == location.get(0) && point.get(1) == location.get(1)) {
sameLocation++;
continue;
}
angles.add(Math.toDegrees(Math.atan2(point.get(1) - location.get(1), point.get(0) - location.get(0))));
}
Collections.sort(angles);
int n = angles.size();
for (int i = 0; i < n; i++) {
angles.add(angles.get(i) + 360);
}
int maxVisible = 0;
for (int start = 0, end = 0; end < angles.size(); end++) {
while (angles.get(end) - angles.get(start) > angle) {
start++;
}
maxVisible = Math.max(maxVisible, end - start + 1);
}
return maxVisible + sameLocation;
}
}Loading editor...