Maximum Number of Visible Points Medium 0 attempts
LeetCode ↗

Maximum Number of Visible Points

Medium Two Pointer LeetCode

Imagine standing at position location on a 2D plane, given an array of points and a viewing angle in degrees. Find the largest number of points that can fit inside your field of view at once. Any point sitting exactly at your own location is always counted as visible and doesn't take up any of your viewing angle.

Edge cases: Points overlapping the location. angle = 360 means all points are visible. All points at the same angle from the location.

Input Format
Implement visiblePoints(points, angle, location). Inputs below show JavaScript function arguments; there is no stdin parsing.
Output Format
Return the result described in the statement.

Sample Input and Output

Example 1 · Run Sample

Input
points = [[2,1],[2,2],[3,3]]
angle = 90
location = [1,1]
Output
3

Example 2

Input
points = [[1,0],[2,1]]
angle = 13
location = [1,1]
Output
1

Example 3

Input
points = [[1,0],[0,1],[-1,0]]
angle = 360
location = [0,0]
Output
3
Constraints
  • 1 <= points.length <= 10^5
  • 1 <= angle <= 360
Test Cases (4)
Case 1
Args: [[[2,1],[2,2],[3,3]],90,[1,1]] Expected: 3
Case 2
Args: [[[1,0],[2,1]],13,[1,1]] Expected: 1
Case 3
Args: [[[1,0],[0,1],[-1,0]],360,[0,0]] Expected: 3
Case 4
Args: [[[0,0]],90,[0,0]] Expected: 1
Topics
Two Pointer

Approach: Polar Angles + Sliding Window

Convert each point to its angle relative to the location using atan2. Sort the angles, then duplicate the array with +360° to handle the wraparound. Slide a window of size angle degrees across the sorted list to find the maximum count. Add points that sit exactly on the location separately since they're always visible.

javascript
function visiblePoints(points, angle, location) {
  const [lx, ly] = location;
  let atLocation = 0;
  const angles = [];

  for (const [px, py] of points) {
    if (px === lx && py === ly) {
      atLocation++;
    } else {
      angles.push(Math.atan2(py - ly, px - lx) * (180 / Math.PI));
    }
  }

  angles.sort((a, b) => a - b);
  const n = angles.length;
  const doubled = [...angles, ...angles.map(a => a + 360)];

  let max = 0;
  let left = 0;

  for (let right = 0; right < doubled.length; right++) {
    while (right - left + 1 > n || doubled[right] - doubled[left] > angle + 1e-9) left++;
    max = Math.max(max, right - left + 1);
  }

  return max + atLocation;
}

Time Complexity: O(n log n) for sorting

Space Complexity: O(n) for the angles array

Saved in this browser only. Private to you.

JavaScript