Leetcode 1610. Maximum Number of Visible Points

Problem Explanation:

In this problem, you are given several points on the X-Y coordinate plane, a location to remain stationary at, and an angle of your field of view. The aim is to figure out the maximum number of points that can be viewed from that location within the given angle of view. All points at your location are always visible and points do not obstruct the view of other points.

The field of view is calculated based on how much you rotate counterclockwise. Let's say d is the angle by which you rotate. So, the field of view goes from [d - angle/2, d + angle/2].

Example:

Let's take a look at an example:

Consider these inputs, points = [[2,1],[2,2],[3,3]], angle = 90, and location = [1,1]

At current location [1,1], let's rotate and find the number of visible points. You find that all points [[2,1],[2,2],[3,3]] are visible within 90 degrees of rotation. So, the maximum number of visible points are 3.

Approach:

The solution to this problem is characterized by the sliding window approach. It starts by calculating the angle between each point and your location, and then sorts these calculated angles.

A window is then slid along these sorted angles, and the other end of the window is stretched as long as the points it contains form an angle that is less than or equal to the given viewing angle. The movement of the window is based on the condition that the point at r - point at l > angle. The largest window size during this process will contain the maximum number of points that can be viewed from your location at a given time.

The solution also considers that there could be points at your own location which are always visible and handles them separately.

Solution:

C++

1
2cpp
3#include <vector>
4#include <algorithm>
5#include <cmath>
6
7class Solution {
8 public:
9  int visiblePoints(std::vector<std::vector<int>>& points, int angle, std::vector<int>& location) {
10    const int posX = location[0];
11    const int posY = location[1];
12    int maxVisible = 0;
13    // For storing points at current location
14    int same = 0;
15    std::vector<double> pointAngles;
16
17    for (const std::vector<int>& p : points) {
18      const int x = p[0];
19      const int y = p[1];
20      // If the point is at location, increment same
21      if (x == posX && y == posY)
22        ++same;
23      else
24        // Calculate the angle of each point with location and push to array
25        pointAngles.push_back(getAngle(y - posY, x - posX));
26    }
27
28    // Sort the array of angles
29    std::sort(begin(pointAngles), end(pointAngles));
30
31    const int n = pointAngles.size();
32    // Add 360 to each point and push to same array, to handle the round up condition.
33    for (int i = 0; i < n; ++i)
34      pointAngles.push_back(pointAngles[i] + 360);
35
36    // Sliding window
37    for (int l = 0, r = 0; r < pointAngles.size(); ++r) {
38      while (pointAngles[r] - pointAngles[l] > angle)
39        // Slide the window
40        ++l;
41      // Update maximum visible points
42      maxVisible = std::max(maxVisible, r - l + 1);
43    }
44    // return maximum visible points including points at location
45    return maxVisible + same;
46  }
47  
48 private:
49  double getAngle(int dy, int dx) {
50    // Function to calculate the angle
51    return atan2(dy, dx) * 180 / M_PI;
52  }
53};

Python

1
2Python
3import math
4from typing import List
5
6class Solution:
7    def visiblePoints(self, points: List[List[int]], angle: int, location: List[int]) -> int:
8        pointAngles, same = [], 0
9        posX, posY = location
10
11        for p in points:
12            x, y = p
13            if x == posX and y == posY:
14                same += 1
15            else:
16                pointAngles.append(math.degrees(math.atan2(y - posY, x - posX)))
17
18        pointAngles.sort()
19        pointAngles = pointAngles + [x + 360 for x in pointAngles]
20
21        l = maxVisible = 0
22        for r in range(len(pointAngles)):
23            while pointAngles[r] - pointAngles[l] > angle:
24                l += 1
25            maxVisible = max(maxVisible, r - l + 1)
26
27        return maxVisible + same

Java

1
2Java
3import java.util.*;
4
5class Solution {
6    public int visiblePoints(List<List<Integer>> points, int angle, List<Integer> location) {
7        List<Double> pointAngles = new ArrayList<>();
8        int posX = location.get(0), posY = location.get(1), same = 0;
9
10        for (List<Integer> point : points) {
11            int x = point.get(0), y = point.get(1);
12            if (x == posX && y == posY) {
13                same++;
14            } else {
15                double angleInDegree = Math.atan2(y - posY, x - posX) * 180 / Math.PI;
16                pointAngles.add(angleInDegree);
17            }
18        }
19
20        Collections.sort(pointAngles);
21        List<Double> tmp = new ArrayList<>(pointAngles);
22        for (double a: pointAngles) {
23            tmp.add(a + 360);
24        }
25        pointAngles = tmp;
26
27        int l = 0, maxVisible = 0;
28        for (int r = 0; r < pointAngles.size(); r++) {
29            while (pointAngles.get(r) - pointAngles.get(l) > angle)
30                l++;
31            maxVisible = Math.max(maxVisible, r - l + 1);
32        }
33
34        return maxVisible + same;
35    }
36}

JavaScript

1
2JavaScript
3var visiblePoints = function(points, angle, location) {
4    let pointAngles = [];
5    let posX = location[0], posY = location[1];
6    let same = 0;
7
8    for (let point of points) {
9        let x = point[0], y = point[1];
10        if (x === posX && y === posY) {
11            same++;
12        } else {
13            pointAngles.push(Math.atan2(y - posY, x - posX) * 180 / Math.PI);
14        }
15    }
16
17    pointAngles.sort((a, b) => a - b);
18
19    for (let i = 0, len = pointAngles.length; i < len; i++)
20        pointAngles.push(pointAngles[i] + 360);
21
22    let l = 0, maxVisible = 0;
23    for (let r = 0; r < pointAngles.length; r++) {
24        while (pointAngles[r] - pointAngles[l] > angle)
25            l++;
26        maxVisible = Math.max(maxVisible, r - l + 1);
27    }
28
29    return maxVisible + same;
30};

These solutions determine the maximum number of points that can be seen from a particular location within a certain field of view. They follow the sliding window approach where the angles of the points with respect to the location are calculated, sorted, and then a window is slid over these angles to determine the maximum number of points.

The C++ and Python solutions provide explicit definitions for helper functions like getAngle and visiblePoints, whereas the Java and JavaScript solutions incorporate all steps within a single method or function.

In each solution, we:

• Extract the location coordinates and initialize a counter for the same-location points
• Iterate through every point in the points list, updating the same-location count if a point is in the same location, otherwise calculating the angle between the point and the location, converting it to degrees, and adding it to the pointAngles list
• Sort the pointAngles list and add another round of angles added by 360 degrees to handle the round-up condition
• Utilize a sliding window approach to keep track of the maximum number of visible points, which is updated whenever a larger window is found
• Return the sum of the maximum number of points from the sliding window and the count of points in the same location

The primary difference across the solutions lies in syntax and language-specific methods for common operations such as sorting a list (Python, JavaScript) or an array (C++), calculating the arctangent of two values (built-in atan2 function in most languages), and converting radians to degrees (C++: 180 / M_PI, Python: math.degrees(), Java and JavaScript: * 180 / Math.PI).

These implementations clearly demonstrate how the logic of a problem-solving approach can be translated across multiple programming languages. Despite syntax differences, the core steps remain the same: calculate angles, sort, slide a window over sorted angles while updating the maximum number, and return this maximum number + the count of same points.