# Maximum Number of Visible Points
**Difficulty:** HARD
[External](https://leetcode.com/problems/maximum-number-of-visible-points)
Canonical: https://scaleengineer.com/dsa/problems/maximum-number-of-visible-points
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math), [Sliding Window](https://scaleengineer.com/dsa/patterns/sliding-window), [Geometry](https://scaleengineer.com/dsa/patterns/geometry)
**Algorithms:** [Sorting](https://scaleengineer.com/algorithms/sorting)
**Data structures:** Array
**Companies:** [Nvidia](https://scaleengineer.com/companies/nvidia), [Anduril](https://scaleengineer.com/companies/anduril), [Applied Intuition](https://scaleengineer.com/companies/applied-intuition), [Nuro](https://scaleengineer.com/companies/nuro)
---
## Problem
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]`.

Your browser does not support the video tag or this video format. 

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:**

![](https://assets.glich.co/dsa/maximum-number-of-visible-points/image0.png) 

**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:**

![](https://assets.glich.co/dsa/maximum-number-of-visible-points/image1.png) 

**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`

# Approaches
## Brute Force by Checking Each Point
This approach iterates through every point, considering it as a potential boundary for the field of view. For each point, it calculates the number of other points that would be visible if the view is aligned with this point. This is repeated for all points to find the maximum.
**Time:** O(N^2), where N is the number of points not at the observer's location. The nested loops to check every angle against every other angle as a potential window start dominate the runtime. · **Space:** O(N), where N is the number of points not at the observer's location. This space is used to store the list of angles.
**Pros:** Simple to understand and implement.; Correctly solves the problem for small input sizes.
**Cons:** The O(N^2) time complexity makes it too slow for large inputs, leading to a 'Time Limit Exceeded' error on platforms like LeetCode.
### Explanation
First, we handle the special case of points that are at the same location as the observer. These points are always visible, so we count them separately and add this count to our final result. For all other points, we calculate the angle they make with the observer's location and the positive x-axis (east direction). We can use `Math.atan2(y - loc_y, x - loc_x)` to get the angle in radians, which we then convert to degrees and normalize to the range `[0, 360)`.

The core of the brute-force idea is to assume that an optimal field of view will have one of the points on its boundary. So, for each calculated angle `a`, we define a viewing window starting at `a` and ending at `a + angle`. We then iterate through all other calculated angles and count how many fall within this `[a, a + angle]` window. A crucial part is handling the "wrap-around" case where `a + angle` exceeds 360 degrees. We keep track of the maximum count found across all possible starting angles. The final result is this maximum count plus the number of points at the observer's location.

```java
import java.util.ArrayList;
import java.util.List;

class Solution {
    public int visiblePoints(List<List<Integer>> points, int angle, List<Integer> location) {
        List<Double> angles = new ArrayList<>();
        int pointsAtLocation = 0;
        int locX = location.get(0);
        int locY = location.get(1);

        for (List<Integer> p : points) {
            int pX = p.get(0);
            int pY = p.get(1);
            if (pX == locX && pY == locY) {
                pointsAtLocation++;
            } else {
                angles.add(calculateAngle(locY, locX, pY, pX));
            }
        }

        int maxPoints = 0;
        // If there are no points other than at the location, the loop won't run and maxPoints will be 0.
        // If there are points, we need to find the max visible in one sweep.
        if (!angles.isEmpty()) {
            maxPoints = 1; // At least one point is visible if the list is not empty
        }

        for (int i = 0; i < angles.size(); i++) {
            double startAngle = angles.get(i);
            double endAngle = startAngle + angle;
            int currentPoints = 0;
            for (int j = 0; j < angles.size(); j++) {
                double otherAngle = angles.get(j);
                // Handle wrap-around case
                if (endAngle >= 360) {
                    if (otherAngle >= startAngle || otherAngle <= endAngle - 360.0) {
                        currentPoints++;
                    }
                } else { // Normal case
                    if (otherAngle >= startAngle && otherAngle <= endAngle) {
                        currentPoints++;
                    }
                }
            }
            maxPoints = Math.max(maxPoints, currentPoints);
        }

        return maxPoints + pointsAtLocation;
    }

    private double calculateAngle(int y1, int x1, int y2, int x2) {
        double angleRad = Math.atan2(y2 - y1, x2 - x1);
        double angleDeg = Math.toDegrees(angleRad);
        if (angleDeg < 0) {
            angleDeg += 360;
        }
        return angleDeg;
    }
}
```
### Algorithm
- 1. Initialize `pointsAtLocation = 0` and a list `angles` to store the angles of points relative to the observer.
- 2. Iterate through each `point` in the input `points` list.
- 3. If a `point` is at the same coordinates as `location`, increment `pointsAtLocation`.
- 4. Otherwise, calculate the angle between the point and the location using `Math.atan2`. Convert this angle from radians to degrees and normalize it to the range `[0, 360)`.
- 5. Add the calculated angle to the `angles` list.
- 6. Initialize `maxPoints = 0`.
- 7. For each `startAngle` in the `angles` list:
    - a. Define a viewing window from `startAngle` to `endAngle = startAngle + angle`.
    - b. Initialize `currentPoints = 0`.
    - c. Iterate through every `otherAngle` in the `angles` list.
    - d. Check if `otherAngle` falls within the `[startAngle, endAngle]` window. This check must handle the circular nature of angles (i.e., when `endAngle` > 360).
    - e. If it's inside the window, increment `currentPoints`.
    - f. After checking all other angles, update `maxPoints = max(maxPoints, currentPoints)`.
- 8. The final result is `maxPoints + pointsAtLocation`.

## Sliding Window on Sorted Circular Angles
This is an optimized approach that avoids the O(N^2) complexity. It involves calculating the angle for each point, sorting these angles, and then using a sliding window technique to find the maximum number of points that can fit within the given `angle` range. The circular nature of angles is handled by duplicating the angle list.
**Time:** O(N log N), where N is the number of points not at the observer's location. The sorting step is the bottleneck. Calculating angles takes O(N), and the sliding window part takes O(N) as each pointer traverses the list only once. · **Space:** O(N), where N is the number of points not at the observer's location. Space is needed for the initial angles list and the extended list for the sliding window.
**Pros:** Highly efficient with O(N log N) time complexity, suitable for large inputs.; The sliding window on a duplicated array is a standard and elegant technique for circular array problems.
**Cons:** Requires extra O(N) space for the duplicated list of angles.; Slightly more complex to conceptualize and implement compared to the brute-force solution.
### Explanation
Similar to the first approach, we first handle points at the observer's location and calculate the angles for all other points, normalizing them to `[0, 360)`. The key insight is that if we sort the angles, we can efficiently find the number of points in any given angular range.

The problem is on a circle, so a view window might "wrap around" from 360 to 0 degrees (e.g., from 350 to 20 degrees). To handle this easily, we create an extended list of angles. We take our sorted list of angles `a1, a2, ..., aN` and append a second copy of each angle incremented by 360: `a1+360, a2+360, ..., aN+360`. This transforms the circular problem into a linear one.

Now, we can apply a sliding window (two-pointer) approach on this new, extended list. We use a `start` pointer and an `end` pointer, both initialized to the beginning. We iterate the `end` pointer through the extended list. For each position of `end`, we advance the `start` pointer until the angle at `start` is within the allowed `angle` degrees from the angle at `end` (i.e., `angles.get(end) - angles.get(start) <= angle`). The number of points in the current valid window is `end - start + 1`. We keep track of the maximum window size found. This maximum size is the maximum number of points visible in any single rotation. We add the count of points at the observer's location to get the final answer.

```java
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

class Solution {
    public int visiblePoints(List<List<Integer>> points, int angle, List<Integer> location) {
        List<Double> angles = new ArrayList<>();
        int pointsAtLocation = 0;
        int locX = location.get(0);
        int locY = location.get(1);

        for (List<Integer> p : points) {
            int pX = p.get(0);
            int pY = p.get(1);
            if (pX == locX && pY == locY) {
                pointsAtLocation++;
            } else {
                angles.add(calculateAngle(locY, locX, pY, pX));
            }
        }

        Collections.sort(angles);

        // To handle wrap-around, duplicate the angles array with +360
        List<Double> circularAngles = new ArrayList<>(angles);
        for (double ang : angles) {
            circularAngles.add(ang + 360.0);
        }

        int maxPoints = 0;
        if (angles.isEmpty()) {
            return pointsAtLocation;
        }

        int start = 0;
        for (int end = 0; end < circularAngles.size(); end++) {
            while (circularAngles.get(end) - circularAngles.get(start) > angle) {
                start++;
            }
            maxPoints = Math.max(maxPoints, end - start + 1);
        }

        return maxPoints + pointsAtLocation;
    }

    private double calculateAngle(int y1, int x1, int y2, int x2) {
        double angleRad = Math.atan2(y2 - y1, x2 - x1);
        double angleDeg = Math.toDegrees(angleRad);
        if (angleDeg < 0) {
            angleDeg += 360;
        }
        return angleDeg;
    }
}
```
### Algorithm
- 1. Separate points at the observer's `location` from other points. Count them in `pointsAtLocation`.
- 2. For each point not at the location, calculate its angle relative to the observer using `Math.atan2`, convert to degrees, and normalize to `[0, 360)`.
- 3. Store these angles in a list.
- 4. Sort the list of angles in ascending order.
- 5. To handle the circular nature of angles, create a new extended list. This list contains the original sorted angles followed by a copy of each angle with 360 added to it.
- 6. Initialize two pointers, `start = 0` and `end = 0`, for the sliding window, and `maxPoints = 0`.
- 7. Iterate with the `end` pointer from the beginning to the end of the extended list.
- 8. Inside the loop, move the `start` pointer forward as long as the angular distance between the points at `end` and `start` is greater than the given `angle` (`angles.get(end) - angles.get(start) > angle`).
- 9. The current number of points in the window is `end - start + 1`. Update `maxPoints = max(maxPoints, end - start + 1)`.
- 10. After the loop, the final answer is `maxPoints + pointsAtLocation`.

# Solutions
### Java

```java
class Solution { public int visiblePoints ( List < List < Integer >> points , int angle , List < Integer > location ) { List < Double > v = new ArrayList <>(); int x = location . get ( 0 ), y = location . get ( 1 ); int same = 0 ; for ( List < Integer > p : points ) { int xi = p . get ( 0 ), yi = p . get ( 1 ); if ( xi == x && yi == y ) { ++ same ; continue ; } v . add ( Math . atan2 ( yi - y , xi - x )); } Collections . sort ( v ); int n = v . size (); for ( int i = 0 ; i < n ; ++ i ) { v . add ( v . get ( i ) + 2 * Math . PI ); } int mx = 0 ; Double t = angle * Math . PI / 180 ; for ( int i = 0 , j = 0 ; j < 2 * n ; ++ j ) { while ( i < j && v . get ( j ) - v . get ( i ) > t ) { ++ i ; } mx = Math . max ( mx , j - i + 1 ); } return mx + same ; } }
```

### CPP

```cpp
class Solution { public: int visiblePoints ( vector < vector < int >>& points , int angle , vector < int >& location ) { vector < double > v ; int x = location [ 0 ], y = location [ 1 ]; int same = 0 ; for ( auto & p : points ) { int xi = p [ 0 ], yi = p [ 1 ]; if ( xi == x && yi == y ) ++ same ; else v . emplace_back ( atan2 ( yi - y , xi - x )); } sort ( v . begin (), v . end ()); int n = v . size (); for ( int i = 0 ; i < n ; ++ i ) v . emplace_back ( v [ i ] + 2 * M_PI ); int mx = 0 ; double t = angle * M_PI / 180 ; for ( int i = 0 , j = 0 ; j < 2 * n ; ++ j ) { while ( i < j && v [ j ] - v [ i ] > t ) ++ i ; mx = max ( mx , j - i + 1 ); } return mx + same ; } };
```

### Python

```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 ] t = angle * pi / 180 mx = max (( bisect_right ( v , v [ i ] + t ) - i for i in range ( n )), default = 0 ) return mx + same
```