Maximum Number of Visible Points solution and explanation
Google
9 more videos on this problem
LeetCode 1610. Maximum Number of Visible PointsHappy Coding · 15:59 · 7K views
LeetCode Solutions 1610. Maximum Number of Visible PointsAbrar & Software Engineering · 12:37 · 4K views
花花酱 LeetCode 1610. Maximum Number of Visible Points - 刷题找工作 EP360Hua Hua · 10:34 · 2K views
Maximum Number of Visible Points Leetcode 1610 Solution using Sliding Window and Polar CoordinatesSuperCode · 27:48 · 2K views
【每日一题】1610. Maximum Number of Visible Points, 10/6/2020Huifeng Guan · 37:35 · 877 views
1610. Maximum Number of Visible Points (Leetcode Medium)Programming Live with Larry · 36:56 · 872 views
1610.Maximum Number of Visible Points | Leetcode Hard | JavaScript | Google | Sliding WindowChristina Deng · 18:00 · 847 views
Leetcode 1610. Maximum Number of Visible PointsAlgorithms for Big Bucks · 7:49 · 237 views
1610. Maximum Number of Visible PointsData Structures & Algorithms Learning · 2:46 · 213 views
1610. Maximum Number of Visible PointsMuerde un zombie · 12:34 · 174 views
The 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:
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.
Constraints:
1 <= points.length <= 105points[i].length == 2location.length == 20 <= angle < 3600 <= posx, posy, xi, yi <= 100
Approach overview
Problem Overview: You are given a set of 2D points, a viewing angle, and your location. The goal is to determine the maximum number of points you can see if you rotate your field of view. A point is visible if the angle between your viewing direction and the point lies within the allowed viewing angle.
The geometric challenge is that visibility depends on direction rather than distance. Each point can be converted into an angle relative to your location using atan2. Once you represent every point as an angle, the problem becomes finding the largest group of angles that fit inside a window of size angle.
Approach 1: Convert to Angles and Use Sliding Window (Two-Pointer Technique) (Time: O(n log n), Space: O(n))
Compute the polar angle of every point relative to your location using atan2(dy, dx). Points located exactly at your position are always visible, so count them separately. Store the remaining angles in an array and sort them. Because viewing directions wrap around at 360°, duplicate the array by appending each angle plus 2π. Then apply a two‑pointer sliding window to find the largest range where the difference between the right and left angles is within the allowed viewing angle. This converts a circular geometry problem into a linear window scan.
The two pointers expand and shrink the window while maintaining the angular constraint. Each pointer moves at most n times, giving linear scanning after sorting. This technique combines geometry, sorting, and a sliding window pattern.
Approach 2: Angular Sweep (Sort and Range Extension) (Time: O(n log n), Space: O(n))
This method also converts every point into an angle relative to the observer. After sorting the angles, extend the array by adding each value plus 2π to handle circular wrap‑around. Instead of explicitly maintaining two pointers, perform an angular sweep where each angle becomes the start of a viewing interval. Use a moving index to find the furthest angle that stays within start + viewAngle. Track the maximum number of points inside that range.
The angular sweep interpretation frames the problem as selecting the densest interval on a circular number line. The main operations are sorting and expanding the window over the extended array. Conceptually this approach is identical to the sliding window technique but emphasizes the geometry interpretation of sweeping angles.
Recommended for interviews: The angle conversion with a sliding window is the expected solution. It shows that you can translate a geometric visibility constraint into a sorted numeric problem and then apply a two‑pointer window efficiently. Interviewers typically want to see correct angle handling, circular wrap‑around using +2π, and separation of points located exactly at the observer.
Approach 1: Convert to Angles and Use Sliding Window (Two-Pointer Technique)
First, convert each point's position into an angle relative to the "east" direction. Handle special cases where points are at the same location as location and account for the circular nature of angles using a sliding window (two-pointer technique).
import math
class Solution:
def maxVisiblePoints(self, points, angle, location):
angles = []
samePosition = 0
x0, y0 = location
for x, y in points:
if x == x0 and y == y0:
samePosition += 1
else:
angles.append(math.atan2(y - y0, x - x0) * 180 / math.pi)
angles.sort()
angles += [a + 360 for a in angles]
maxPoints = 0
left = 0
for right in range(len(angles)):
while angles[right] - angles[left] > angle:
left += 1
maxPoints = max(maxPoints, right - left + 1)
return maxPoints + samePositionimport java.util.*;
public class Solution {
public int maxVisiblePoints(List<List<Integer>> points, int angle, List<Integer> location) {
List<Double> angles = new ArrayList<>();
int sameLocationCount = 0;
int x0 = location.get(0), y0 = location.get(1);
for (List<Integer> point : points) {
int x = point.get(0), y = point.get(1);
if (x == x0 && y == y0) {
sameLocationCount++;
} else {
angles.add(Math.atan2(y - y0, x - x0) * 180 / Math.PI);
}
}
Collections.sort(angles);
int size = angles.size();
for (int i = 0; i < size; i++) {
angles.add(angles.get(i) + 360);
}
int maxVisible = 0, left = 0;
for (int right = 0; right < angles.size(); right++) {
while (angles.get(right) - angles.get(left) > angle) {
left++;
}
maxVisible = Math.max(maxVisible, right - left + 1);
}
return maxVisible + sameLocationCount;
}
}#include <vector>
#include <cmath>
#include <algorithm>
using namespace std;
int maxVisiblePoints(vector<vector<int>>& points, int angle, vector<int>& location) {
vector<double> angles;
int coincidentCount = 0;
int x0 = location[0], y0 = location[1];
for (auto& point : points) {
int x = point[0], y = point[1];
if (x == x0 && y == y0) {
coincidentCount++;
} else {
angles.push_back(atan2(y - y0, x - x0) * 180 / M_PI);
}
}
sort(angles.begin(), angles.end());
int n = angles.size();
for (int i = 0; i < n; ++i) {
angles.push_back(angles[i] + 360);
}
int maxVisible = 0, left = 0;
for (int right = 0; right < angles.size(); ++right) {
while (angles[right] - angles[left] > angle) {
left++;
}
maxVisible = max(maxVisible, right - left + 1);
}
return maxVisible + coincidentCount;
}var maxVisiblePoints = function(points, angle, location) {
let angles = [];
let coincidentCount = 0;
let [x0, y0] = location;
for (let [x, y] of points) {
if (x === x0 && y === y0) {
coincidentCount++;
} else {
angles.push(Math.atan2(y - y0, x - x0) * 180 / Math.PI);
}
}
angles.sort((a, b) => a - b);
angles.push(...angles.map(a => a + 360));
let left = 0;
let maxVisible = 0;
for (let right = 0; right < angles.length; right++) {
while (angles[right] - angles[left] > angle) {
left++;
}
maxVisible = Math.max(maxVisible, right - left + 1);
}
return maxVisible + coincidentCount;
};#include <stdio.h>
#include <math.h>
#include <stdlib.h>
int compare(const void *a, const void *b) {
return (*(double*)a > *(double*)b) - (*(double*)a < *(double*)b);
}
int maxVisiblePoints(int** points, int pointsSize, int* pointsColSize, int angle, int* location) {
double angles[pointsSize * 2];
int coincidentCount = 0;
int index = 0;
int locX = location[0], locY = location[1];
for (int i = 0; i < pointsSize; i++) {
int px = points[i][0], py = points[i][1];
if (px == locX && py == locY) {
coincidentCount++;
} else {
double angle = atan2(py - locY, px - locX) * 180 / M_PI;
angles[index++] = angle;
}
}
qsort(angles, index, sizeof(double), compare);
for (int i = 0; i < index; i++) {
angles[index + i] = angles[i] + 360;
}
int maxVisible = 0;
int left = 0;
for (int right = 0; right < index * 2; right++) {
while (angles[right] - angles[left] > angle) {
left++;
}
maxVisible = fmax(maxVisible, right - left + 1);
}
return maxVisible + coincidentCount;
}using System;
using System.Collections.Generic;
public class Solution {
public int MaxVisiblePoints(IList<IList<int>> points, int angle, IList<int> location) {
List<double> angles = new List<double>();
int samePosition = 0;
int x0 = location[0], y0 = location[1];
foreach (var point in points) {
int x = point[0], y = point[1];
if (x == x0 && y == y0) {
samePosition++;
} else {
angles.Add(Math.Atan2(y - y0, x - x0) * 180 / Math.PI);
}
}
angles.Sort();
List<double> extendedAngles = new List<double>(angles);
extendedAngles.AddRange(angles.ConvertAll(a => a + 360));
int maxVisible = 0, left = 0;
for (int right = 0; right < extendedAngles.Count; right++) {
while (extendedAngles[right] - extendedAngles[left] > angle) {
left++;
}
maxVisible = Math.Max(maxVisible, right - left + 1);
}
return maxVisible + samePosition;
}
}This Python solution examines how angles relative to straight east are found and adjusted using trigonometry. Points on the same origin are automatically included to determine maximum view possible.
Time Complexity: O(n log n) as sorting dominates.
Space Complexity: O(n) to keep all combined angles.
Approach 2: Angular Sweep (Sort and Range Extension)
Transform all points (except those at the observer's location) to angles and sort them. Utilize circular nature by extending angle listings and implement a two-pointer technique akin to a sliding window algorithm in order to obtain max visible within a bounded view.
import math
class Solution:
def maxVisiblePoints(self, points, angle, location):
angles = []
samePosition = 0
x0, y0 = location
for x, y in points:
if x == x0 and y == y0:
samePosition += 1
else:
angles.append(math.atan2(y - y0, x - x0) * 180 / math.pi)
angles.sort()
angles += [a + 360 for a in angles]
maxPoints = 0
left = 0
for right in range(len(angles)):
while angles[right] - angles[left] > angle:
left += 1
maxPoints = max(maxPoints, right - left + 1)
return maxPoints + samePositionimport java.util.*;
public class Solution {
public int maxVisiblePoints(List<List<Integer>> points, int angle, List<Integer> location) {
List<Double> angles = new ArrayList<>();
int sameLocationCount = 0;
int x0 = location.get(0), y0 = location.get(1);
for (List<Integer> point : points) {
int x = point.get(0), y = point.get(1);
if (x == x0 && y == y0) {
sameLocationCount++;
} else {
angles.add(Math.atan2(y - y0, x - x0) * 180 / Math.PI);
}
}
Collections.sort(angles);
int size = angles.size();
for (int i = 0; i < size; i++) {
angles.add(angles.get(i) + 360);
}
int maxVisible = 0, left = 0;
for (int right = 0; right < angles.size(); right++) {
while (angles.get(right) - angles.get(left) > angle) {
left++;
}
maxVisible = Math.max(maxVisible, right - left + 1);
}
return maxVisible + sameLocationCount;
}
}#include <vector>
#include <cmath>
#include <algorithm>
using namespace std;
int maxVisiblePoints(vector<vector<int>>& points, int angle, vector<int>& location) {
vector<double> angles;
int coincidentCount = 0;
int x0 = location[0], y0 = location[1];
for (auto& point : points) {
int x = point[0], y = point[1];
if (x == x0 && y == y0) {
coincidentCount++;
} else {
angles.push_back(atan2(y - y0, x - x0) * 180 / M_PI);
}
}
sort(angles.begin(), angles.end());
int n = angles.size();
for (int i = 0; i < n; ++i) {
angles.push_back(angles[i] + 360);
}
int maxVisible = 0, left = 0;
for (int right = 0; right < angles.size(); ++right) {
while (angles[right] - angles[left] > angle) {
left++;
}
maxVisible = max(maxVisible, right - left + 1);
}
return maxVisible + coincidentCount;
}var maxVisiblePoints = function(points, angle, location) {
let angles = [];
let coincidentCount = 0;
let [x0, y0] = location;
for (let [x, y] of points) {
if (x === x0 && y === y0) {
coincidentCount++;
} else {
angles.push(Math.atan2(y - y0, x - x0) * 180 / Math.PI);
}
}
angles.sort((a, b) => a - b);
angles.push(...angles.map(a => a + 360));
let left = 0;
let maxVisible = 0;
for (let right = 0; right < angles.length; right++) {
while (angles[right] - angles[left] > angle) {
left++;
}
maxVisible = Math.max(maxVisible, right - left + 1);
}
return maxVisible + coincidentCount;
};#include <stdio.h>
#include <math.h>
#include <stdlib.h>
int compare(const void *a, const void *b) {
return (*(double*)a > *(double*)b) - (*(double*)a < *(double*)b);
}
int maxVisiblePoints(int** points, int pointsSize, int* pointsColSize, int angle, int* location) {
double angles[pointsSize * 2];
int coincidentCount = 0;
int index = 0;
int locX = location[0], locY = location[1];
for (int i = 0; i < pointsSize; i++) {
int px = points[i][0], py = points[i][1];
if (px == locX && py == locY) {
coincidentCount++;
} else {
double newAngle = atan2(py - locY, px - locX) * 180 / M_PI;
angles[index++] = newAngle;
}
}
qsort(angles, index, sizeof(double), compare);
for (int i = 0; i < index; i++) {
angles[index + i] = angles[i] + 360;
}
int maxVisible = 0;
int left = 0;
for (int right = 0; right < index * 2; right++) {
while (angles[right] - angles[left] > angle) {
left++;
}
maxVisible = fmax(maxVisible, right - left + 1);
}
return maxVisible + coincidentCount;
}using System;
using System.Collections.Generic;
public class Solution {
public int MaxVisiblePoints(IList<IList<int>> points, int angle, IList<int> location) {
List<double> angles = new List<double>();
int samePosition = 0;
int x0 = location[0], y0 = location[1];
foreach (var point in points) {
int x = point[0], y = point[1];
if (x == x0 && y == y0) {
samePosition++;
} else {
angles.Add(Math.Atan2(y - y0, x - x0) * 180 / Math.PI);
}
}
angles.Sort();
List<double> extendedAngles = new List<double>(angles);
extendedAngles.AddRange(angles.ConvertAll(a => a + 360));
int maxVisible = 0, left = 0;
for (int right = 0; right < extendedAngles.Count; right++) {
while (extendedAngles[right] - extendedAngles[left] > angle) {
left++;
}
maxVisible = Math.Max(maxVisible, right - left + 1);
}
return maxVisible + samePosition;
}
}This Python implementation respects patterns inherent in computational circles, visually widening through devised angular representation. Duplication accomplishes prospect depth for calculated overfullness in point seeing.
Time Complexity: O(n log n) due to angle allocation and ordering.
Space Complexity: O(n) for comprehensive mirrored angular split arrangement.
Approach 3: Default Approach
func visiblePoints(points [][]int, angle int, location []int) int {
same := 0
v := []float64{}
for _, p := range points {
if p[0] == location[0] && p[1] == location[1] {
same++
} else {
v = append(v, math.Atan2(float64(p[1]-location[1]), float64(p[0]-location[0])))
}
}
sort.Float64s(v)
for _, deg := range v {
v = append(v, deg+2*math.Pi)
}
mx := 0
t := float64(angle) * math.Pi / 180
for i, j := 0, 0; j < len(v); j++ {
for i < j && v[j]-v[i] > t {
i++
}
mx = max(mx, j-i+1)
}
return same + mx
}Complexity comparison
| Approach | Complexity |
|---|---|
| Convert to Angles and Use Sliding Window (Two-Pointer Technique) | Time Complexity: O(n log n) as sorting dominates. |
| Angular Sweep (Sort and Range Extension) | Time Complexity: O(n log n) due to angle allocation and ordering. |
| Default Approach | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Convert to Angles + Sliding Window | O(n log n) | O(n) | General case. Clean two-pointer implementation after sorting angles. |
| Angular Sweep with Range Extension | O(n log n) | O(n) | When reasoning about geometry and circular intervals is clearer. |
Frequently asked questions
Is Maximum Number of Visible Points easy or hard?
Maximum Number of Visible Points is classified as Hard on LeetCode. The difficulty comes from translating a geometric visibility problem into an angle‑sorting problem and correctly handling circular wrap‑around with a sliding window.
Maximum Number of Visible Points Python/Java solution
Python and Java implementations follow the same steps: compute angles with atan2, sort the list, duplicate angles with +2π for circular handling, then apply a sliding window to count points within the viewing angle. The algorithm runs in O(n log n) time.
How to solve Maximum Number of Visible Points in O(n)?
Pure O(n) is not achievable because the angles must be sorted to efficiently check contiguous ranges. After sorting in O(n log n), a two‑pointer sliding window scans the array in O(n) time to find the maximum number of angles within the allowed viewing range.
What is the best approach for Maximum Number of Visible Points?
The optimal approach converts every point into its polar angle relative to the observer using atan2, sorts the angles, and applies a sliding window to find the largest range within the viewing angle. To handle circular wrap‑around, duplicate angles by adding 2π. The overall complexity is O(n log n) due to sorting.
Is Maximum Number of Visible Points asked at Google/Amazon/Meta?
Geometry and angle‑based window problems similar to Maximum Number of Visible Points appear in interviews at companies like Google, Amazon, and Meta. They test spatial reasoning, sorting, and sliding window techniques combined with trigonometric calculations.
What data structure is used in Maximum Number of Visible Points?
The solution mainly uses arrays or lists to store computed angles. After sorting the array, a two‑pointer sliding window scans the values. Mathematical functions such as atan2 are used to convert coordinates into angles.
What is the time complexity of Maximum Number of Visible Points?
The standard solution runs in O(n log n) time and O(n) space. Sorting the computed angles dominates the runtime, while the sliding window or angular sweep itself runs in linear O(n) time.