LeetCode 1610 - Maximum Number of Visible Points

In this problem, we are standing at a fixed position on a 2D plane, represented by location = [posx, posy]. Around us, there are multiple points, each with integer coordinates. We are allowed to rotate in place, but we cannot move.

leetcodehardarraymathgeometrysliding-windowsorting

LeetCode Problem 1610

Difficulty: 🔴 Hard
Topics: Array, Math, Geometry, Sliding Window, Sorting

Solution

Problem Understanding

In this problem, we are standing at a fixed position on a 2D plane, represented by location = [posx, posy]. Around us, there are multiple points, each with integer coordinates. We are allowed to rotate in place, but we cannot move.

Our vision works like a camera with a limited viewing angle. The parameter angle tells us how wide the field of view is. If we rotate to some direction d, then we can see every point whose direction relative to us falls within the inclusive angular interval:

$$[d - \tfrac{\text{angle}}{2},\ d + \tfrac{\text{angle}}{2}]$$

The goal is to determine the maximum number of points visible at the same time for some rotation direction.

The important geometric detail is that visibility depends only on the angle from our position to each point. Distance does not matter. Multiple points can overlap at the same coordinates, and points do not block each other.

Points located exactly at our own position are always visible, regardless of rotation. These points require special handling because their direction is undefined.

The constraints are large:

  • Up to 10^5 points
  • Coordinates are small integers, but the number of points is large
  • The solution must be significantly better than quadratic time

This immediately rules out any algorithm that compares every pair of points or tries every possible viewing direction naively.

Several edge cases are especially important:

  • Points located exactly at location
  • Angles near the 0° / 360° boundary
  • Duplicate directions
  • angle = 0, where only points in exactly the same direction can be seen together
  • Very large viewing angles close to 360°

The circular nature of angles is the main challenge in this problem.

Approaches

Brute Force Approach

A straightforward solution is to treat every point direction as a possible center of the viewing window.

For each candidate direction:

  1. Compute the angular direction to every other point
  2. Count how many fall within the viewing range
  3. Track the maximum count

This works because the optimal viewing direction must align with some point boundary. However, if there are n points, then for every point we may scan all others, leading to O(n^2) time complexity.

With n = 10^5, quadratic time is far too slow.

Key Insight

The key observation is that every point can be represented by a single angle relative to the observer.

Using atan2(dy, dx), we can convert each point into an angle in degrees. Once all points are represented this way:

  • The problem becomes finding the largest group of angles inside a window of size angle
  • After sorting the angles, the visible points form a contiguous segment

This transforms the geometry problem into a sliding window problem on a sorted array.

The remaining complication is circular wraparound. For example:

  • One point may have angle 359°
  • Another may have angle 1°

These points are actually only 2° apart, but in sorted order they appear far away.

We solve this by duplicating the angle list with +360° added to each angle. This linearizes the circular structure and allows a standard sliding window.

Approach Comparison

Approach Time Complexity Space Complexity Notes
Brute Force O(n²) O(n) Try every viewing direction and count visible points
Optimal O(n log n) O(n) Sort angles and use sliding window

Algorithm Walkthrough

Step 1: Separate coincident points

Points located exactly at location are always visible.

For each point:

  • If (x, y) == location, increment same_position
  • Otherwise, process its direction normally

We store the always-visible points separately because they do not participate in angular calculations.

Step 2: Convert points into angles

For every remaining point:

  1. Compute:

$$dx = x - posx$$

$$dy = y - posy$$ 2. Compute the angle using:

$$\theta = \text{atan2}(dy, dx)$$

The atan2 function correctly handles all quadrants and returns the angle in radians.

  1. Convert radians to degrees.

We now have a list of directional angles.

Step 3: Sort the angles

Sorting places all directions in increasing order.

This is essential because any visible set of points must appear consecutively in angular order.

Step 4: Handle circular wraparound

Angles are circular.

For example:

  • 359°
  • 1°

These are close geometrically but far apart numerically.

To handle this cleanly:

  • Duplicate every angle with +360°
  • Append these new values to the array

Example:

Original:
[1, 45, 359]

Extended:
[1, 45, 359, 361, 405, 719]

Now every valid viewing window becomes a standard contiguous interval.

Step 5: Use a sliding window

Maintain two pointers:

  • left
  • right

Expand right through the extended array.

While:

$$angles[right] - angles[left] > angle$$

move left forward.

At every step:

$$window_size = right - left + 1$$

Track the maximum window size.

This gives the maximum number of visible directional points.

Step 6: Add coincident points

Finally:

answer = best_window + same_position

because coincident points are always visible.

Why it works

After sorting, every group of visible points corresponds to a contiguous interval of angles. The sliding window maintains the invariant that all points inside the window differ by at most angle degrees.

Duplicating the array with +360° converts the circular geometry into a linear interval problem, ensuring that wraparound visibility is handled correctly.

Because every possible valid interval is examined exactly once by the sliding window, the algorithm always finds the optimal answer.

Python Solution

from typing import List
import math

class Solution:
    def visiblePoints(self, points: List[List[int]], angle: int, location: List[int]) -> int:
        same_position = 0
        angles = []

        posx, posy = location

        for x, y in points:
            if x == posx and y == posy:
                same_position += 1
            else:
                dx = x - posx
                dy = y - posy

                degree = math.degrees(math.atan2(dy, dx))
                angles.append(degree)

        angles.sort()

        extended_angles = angles + [a + 360 for a in angles]

        max_visible = 0
        left = 0

        for right in range(len(extended_angles)):
            while extended_angles[right] - extended_angles[left] > angle:
                left += 1

            max_visible = max(max_visible, right - left + 1)

        return max_visible + same_position

The implementation begins by separating points located exactly at the observer's position. These points are counted immediately because they are always visible.

For every other point, the code computes the directional angle using atan2. The use of math.degrees converts radians into degrees so comparisons match the problem statement directly.

After sorting the angle list, the implementation constructs extended_angles by appending each angle shifted by 360. This removes the complexity of circular wraparound.

The sliding window then scans through the extended array. The left pointer advances whenever the angular span exceeds the allowed viewing angle.

At every iteration, the current window represents a valid visible set of points. The algorithm tracks the largest such window and finally adds the always-visible coincident points.

Go Solution

package main

import (
	"math"
	"sort"
)

func visiblePoints(points [][]int, angle int, location []int) int {
	posx, posy := location[0], location[1]

	samePosition := 0
	angles := make([]float64, 0)

	for _, point := range points {
		x, y := point[0], point[1]

		if x == posx && y == posy {
			samePosition++
		} else {
			dx := float64(x - posx)
			dy := float64(y - posy)

			degree := math.Atan2(dy, dx) * 180.0 / math.Pi
			angles = append(angles, degree)
		}
	}

	sort.Float64s(angles)

	extended := make([]float64, 0, len(angles)*2)
	extended = append(extended, angles...)

	for _, a := range angles {
		extended = append(extended, a+360.0)
	}

	maxVisible := 0
	left := 0

	for right := 0; right < len(extended); right++ {
		for extended[right]-extended[left] > float64(angle) {
			left++
		}

		windowSize := right - left + 1
		if windowSize > maxVisible {
			maxVisible = windowSize
		}
	}

	return maxVisible + samePosition
}

The Go implementation follows the same algorithmic structure as the Python version.

One notable difference is explicit floating-point conversion. Since Go distinguishes integers and floating-point values strictly, dx and dy must be converted to float64 before calling math.Atan2.

Go also requires manual slice construction for the duplicated angle array. The sliding window logic remains identical.

No integer overflow concerns exist because coordinates are small and all angle calculations use floating-point arithmetic.

Worked Examples

Example 1

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

Step 1: Compute angles

Point dx dy Angle
[2,1] 1 0 0°
[2,2] 1 1 45°
[3,3] 2 2 45°

Sorted angles:

[0, 45, 45]

Extended array:

[0, 45, 45, 360, 405, 405]

Step 2: Sliding window

right Value left Window Size
0 0 0 [0] 1
1 45 0 [0,45] 2
2 45 0 [0,45,45] 3

Maximum visible points:

3

Example 2

points = [[2,1],[2,2],[3,4],[1,1]]
angle = 90
location = [1,1]

Point [1,1] is at the observer location.

same_position = 1

Computed angles

Point Angle
[2,1] 0°
[2,2] 45°
[3,4] 56.31°

Sliding window finds all three visible simultaneously.

Final answer:

3 + 1 = 4

Example 3

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

Computed angles

Point Angle
[1,0] -90°
[2,1] 0°

Difference:

90°

This exceeds the viewing angle 13°.

Maximum visible:

1

Complexity Analysis

Measure Complexity Explanation
Time O(n log n) Sorting dominates the runtime
Space O(n) Storing angles and duplicated array

The algorithm processes each point once to compute angles, requiring O(n) work. Sorting the angle list requires O(n log n) time, which dominates the complexity.

The sliding window itself is linear because each pointer moves at most n times.

Space usage is linear because we store the angle array and its duplicated version.

Test Cases

from typing import List

class Solution:
    def visiblePoints(self, points: List[List[int]], angle: int, location: List[int]) -> int:
        import math

        same_position = 0
        angles = []

        posx, posy = location

        for x, y in points:
            if x == posx and y == posy:
                same_position += 1
            else:
                degree = math.degrees(math.atan2(y - posy, x - posx))
                angles.append(degree)

        angles.sort()

        extended = angles + [a + 360 for a in angles]

        left = 0
        best = 0

        for right in range(len(extended)):
            while extended[right] - extended[left] > angle:
                left += 1

            best = max(best, right - left + 1)

        return best + same_position

sol = Solution()

assert sol.visiblePoints([[2,1],[2,2],[3,3]], 90, [1,1]) == 3
# Basic example with overlapping directions

assert sol.visiblePoints([[2,1],[2,2],[3,4],[1,1]], 90, [1,1]) == 4
# Includes point at observer location

assert sol.visiblePoints([[1,0],[2,1]], 13, [1,1]) == 1
# Narrow viewing angle

assert sol.visiblePoints([[1,1]], 0, [1,1]) == 1
# Single coincident point

assert sol.visiblePoints([[2,1],[3,1],[4,1]], 0, [1,1]) == 3
# Multiple points in exactly same direction

assert sol.visiblePoints([[0,1],[1,0]], 90, [0,0]) == 2
# Boundary inclusion should count both

assert sol.visiblePoints([[1,0],[0,1],[-1,0]], 180, [0,0]) == 3
# Large angle spanning half-circle

assert sol.visiblePoints([[1,0],[-1,0]], 0, [0,0]) == 1
# Opposite directions with zero angle

assert sol.visiblePoints([[1,0],[0,-1]], 270, [0,0]) == 2
# Very wide viewing angle

assert sol.visiblePoints([[2,2],[2,2],[2,2]], 0, [1,1]) == 3
# Duplicate points same direction

assert sol.visiblePoints([[1,0],[0,1],[-1,0],[0,-1]], 359, [0,0]) == 4
# Nearly full-circle visibility

Test Summary

Test Why
Basic sample Verifies standard visibility calculation
Point at observer Ensures coincident points are always counted
Narrow angle Verifies restrictive viewing windows
Single coincident point Smallest valid input
Same direction points Ensures duplicates are counted
Boundary inclusion Verifies inclusive angle handling
Half-circle visibility Tests large windows
Opposite directions Ensures exact-angle handling
Wide angle Tests near-complete visibility
Duplicate coordinates Ensures repeated points work correctly
359-degree field Tests wraparound correctness

Edge Cases

One important edge case occurs when points are located exactly at the observer's position. These points do not have a meaningful direction because the vector from the observer to the point is zero. A naive implementation might incorrectly attempt to compute an angle for them, leading to undefined behavior. The solution avoids this entirely by counting such points separately and adding them to the final result.

Another critical edge case involves wraparound near 0° and 360°. For example, points at 359° and 1° are only two degrees apart geometrically, but numerically they appear far apart. Without duplicating the angle array using +360°, the sliding window would fail to detect these valid intervals. The extended array transforms the circular problem into a linear one.

A third subtle case occurs when angle = 0. In this situation, only points with exactly identical directions can be viewed together. Floating-point inaccuracies could potentially introduce bugs here. However, because all angles are computed consistently using atan2, identical directions produce equal floating-point values, allowing the sliding window comparison to work correctly.

Another important scenario is when multiple points share the same direction but lie at different distances. Since visibility depends only on angle, not distance, all such points should be counted simultaneously. The algorithm naturally handles this because points with the same direction occupy the same position in sorted angular order.