Abstract / Summary

Given a set of points, find the maximum number of points you can see from any single point by drawing lines in four main directions.

Note

The full problem description, including helpful examples, can be found on LeetCode.

This problem is ranked as

and has an acceptance rate of about 38% (100k+ submissions).

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.

Overview

The visiblePoints method determines the maximum number of points that can be observed from a fixed camera location when the camera can rotate within a given angular field of view. The input consists of a list of 2-dimensional points, an integer angle representing the camera’s field of view in degrees, and a location specifying the camera’s coordinates. The algorithm treats points that coincide with the camera as always visible and computes angular positions for all other points relative to the camera. By sorting these angles and using a sliding window, it finds the largest subset that fits inside any interval of length angle.

Key Steps

Extracting the camera coordinates and initializing counters

x, y = location
always = 0

The camera’s x- and y-coordinates are unpacked for later use. A counter always is prepared to record points that lie exactly at the camera’s location, because such points are visible regardless of the camera’s orientation.

Converting points to angular directions

direction = []
for px, py in points:
    if px == x and py == y:
        always += 1
    else:
        dx = px - x
        dy = py - y
        alpha = (180 / pi) * atan2(dy, dx)
        direction.append(alpha)
        direction.append(alpha + 360)

For each point that is not colocated with the camera, the vector from the camera to the point (dx, dy) is formed. The atan2 function yields the angle in radians, which is then converted to degrees. Two entries are stored for each point: the original angle and the same angle shifted by 360 degrees. The duplication enables a seamless handling of the circular wrap-around when the sliding window crosses the 0/360 degree boundary.

Sorting the angular list

direction.sort()

Sorting places the angles in ascending order, which is a prerequisite for the linear scan that follows. Because each original angle appears twice (once with a 360-degree offset), the sorted list contains a contiguous representation of the circular angle space.

Sliding window to find the maximal visible set

result  = 0
right   = 0
for left in range(len(direction) // 2):
    low  = direction[left]
    high = angle + low

    while right < len(direction) and direction[right] <= high:
        right += 1

    result = max(result, right - left)

The outer loop iterates over the first half of the sorted list, which corresponds to the original angles before duplication. For each left index, the algorithm defines a window that starts at low and extends angle degrees forward to high. The inner while loop advances the right pointer as long as the angle at right remains within the window. The size of the window (right - left) represents the number of points that can be seen when the camera is oriented to start at low. The maximum window size encountered during the scan is stored in result.

Adding always-visible points to the final answer

return result + always

After the sliding window computation, the method adds the count of points that coincide with the camera location, because they are visible irrespective of the camera’s orientation.

Edge Cases Handled

The implementation explicitly checks for points that share the exact coordinates of the camera. By incrementing always for such points and excluding them from angular calculations, the algorithm ensures they are counted in the final result without affecting the sliding window logic.

The duplication of each angle with a 360-degree offset addresses the scenario where the optimal viewing interval straddles the 0/360 degree seam. Without this duplication, a window that starts near 350 degrees and extends past 0 degrees would be incorrectly split, potentially missing points that are actually within the field of view. The duplicated entries guarantee that any interval of length angle can be represented as a contiguous segment in the sorted list.

The loop bounds (range(len(direction) // 2)) guarantee that the sliding window only starts from the original set of angles, preventing the algorithm from counting the same point twice while still allowing the window to extend into the duplicated region.

Performance Optimizations

The algorithm achieves linearithmic performance by sorting the angular list once and then scanning it with a two-pointer technique. The sorting step orders the angles, enabling the subsequent sliding window to move monotonically forward; the right pointer never retreats, which ensures that each element is examined at most twice-once when it becomes the left boundary and once when it becomes the right boundary. This eliminates the need for nested loops that would otherwise lead to quadratic work.

Duplicating each angle with a 360-degree offset doubles the size of the list, but this trade-off simplifies wrap-around handling and avoids additional conditional logic inside the inner loop. The extra memory usage is linear in the number of points and does not affect the asymptotic time behavior.

By separating points that coincide with the camera from the angular processing, the method avoids unnecessary trigonometric calculations for those points, reducing computational overhead for inputs that contain many such coincidences.

Imagine there is a big room filled with toys scattered all over the floor. You are standing in one spot with a special toy camera that can only see things within a certain slice of the room. Think of this slice like a pizza wedge.

First, you look at all the toys to see if any are sitting exactly where you are standing. If a toy is right under your feet, you can see it no matter which way you point your camera, so you count these up and keep them tucked away in a safe spot for later.

Next, you look at all the other toys that are further away. You figure out what angle each toy is at compared to where you are standing. Because your camera can spin around in a full circle, you make a list of these angles, and you even add some extra ones to represent the circle going all the way around so nothing gets missed.

Once you have your list of angles, you line them up from smallest to largest, just like sorting toys by size. Now you can use your camera wedge to see how many toys fit inside. You slide your wedge around the circle, keeping track of how many toys you can see at once. Every time you find a spot that lets you see more toys than before, you remember that number.

Finally, you add the toys you found under your own feet to the highest number of toys you saw through your camera lens. That total gives you the maximum number of toys you can see altogether.

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):

Time: loglinear
As a rule of thumb, the maximum input size for one second execution time is

• factorial: up to 10 elements
• exponential: up to 20 elements
• polynomial: a few thousand elements
• loglinear: up to 100,000 elements
• linear: a few million elements
• logarithmic: a billion elements
• constant: practically unlimited

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)

	author
author	solutions
www	AlgoMonster	C++		Java			Python	TS
	WalkCCC	C++		Java			Python
	leetcode.ca	C++		Java		Go	Python
	Progiez	C++		Java			Python
github	black-shadows	C++
	charles-wangkai			Java
	everthis		JS
	fsq	C++
	JoshCrozier		JS
	keineahnung2345	C++
	suxrobGM				C#
	wisdompeak	C++
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, Go, Java, Python
Progiez	C++, Java, Python
black-shadows	C++, C++
charles-wangkai	Java
everthis	JavaScript
fsq	C++
JoshCrozier	JavaScript
keineahnung2345	C++
suxrobGM	C#
wisdompeak	C++

There are a few extra pages giving you some insights into my setup:

• Tech Stack - my development environment and tools
• AI - how AI helped me create this website (NOT solving the problems)
• Progress - progression over time
• Quality - code quality