Maximum Number of Visible Points Medium 0 attempts
LeetCode ↗

Maximum Number of Visible Points

Medium Two Pointer LeetCode

You are standing at location on a 2D plane. Given an array of points and a viewing angle (in degrees), return the maximum number of points you can see within your field of view. Points at your exact location are always visible and don't consume any viewing angle.

Example 1:

Input: points = [[2,1],[2,2],[3,3]], angle = 90, location = [1,1]
Output: 3
Explanation: All three points fall within a 90° field of view.

Example 2:

Input: points = [[2,1],[2,2],[3,4],[1,1]], angle = 90, location = [1,1]
Output: 4
Explanation: [1,1] is at the location itself (always counted), plus the other 3 fit in the 90° window.

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

Sample Input
points = [[2,1],[2,2],[3,3]], angle = 90, location = [1,1]
Sample Output
3
Constraints
  • 1 <= points.length <= 10^5
  • 1 <= angle <= 360
Test Cases
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
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.

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 (doubled[right] - doubled[left] > angle) 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