LeetCode #1610 — HARD

Maximum Number of Visible Points

Break down a hard problem into reliable checkpoints, edge-case handling, and complexity trade-offs.

Solve on LeetCode
The Problem

Problem Statement

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].

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 <= 105
  • points[i].length == 2
  • location.length == 2
  • 0 <= angle < 360
  • 0 <= posx, posy, xi, yi <= 100
Patterns Used
🪟Sliding Window→

Roadmap

  1. Brute Force Baseline
  2. Core Insight
  3. Algorithm Walkthrough
  4. Edge Cases
  5. Full Annotated Code
  6. Interactive Study Demo
  7. Complexity Analysis
Step 01

Brute Force Baseline

Problem summary: 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.

Baseline thinking

Start with the most direct exhaustive search. That gives a correctness anchor before optimizing.

Pattern signal: Array · Math · Sliding Window

Example 1

[[2,1],[2,2],[3,3]]
90
[1,1]

Example 2

[[2,1],[2,2],[3,4],[1,1]]
90
[1,1]

Example 3

[[1,0],[2,1]]
13
[1,1]
Step 02

Core Insight

What unlocks the optimal approach

  • Sort the points by polar angle with the original position. Now only a consecutive collection of points would be visible from any coordinate.
  • We can use two pointers to keep track of visible points for each start point
  • For handling the cyclic condition, it’d be helpful to append the point list to itself after sorting.
Interview move: turn each hint into an invariant you can check after every iteration/recursion step.
Step 03

Algorithm Walkthrough

Iteration Checklist

  1. Define state (indices, window, stack, map, DP cell, or recursion frame).
  2. Apply one transition step and update the invariant.
  3. Record answer candidate when condition is met.
  4. Continue until all input is consumed.
Use the first example testcase as your mental trace to verify each transition.
Step 04

Edge Cases

Minimum Input
Single element / shortest valid input
Validate boundary behavior before entering the main loop or recursion.
Duplicates & Repeats
Repeated values / repeated states
Decide whether duplicates should be merged, skipped, or counted explicitly.
Extreme Constraints
Largest constraint values
Re-check complexity target against constraints to avoid time-limit issues.
Invalid / Corner Shape
Empty collections, zeros, or disconnected structures
Handle special-case structure before the core algorithm path.
Step 05

Full Annotated Code

Source-backed implementations are provided below for direct study and interview prep.

// Accepted solution for LeetCode #1610: Maximum Number of Visible Points
class Solution {
    public int visiblePoints(List<List<Integer>> points, int angle, List<Integer> location) {
        List<Double> v = new ArrayList<>();
        int x = location.get(0), y = location.get(1);
        int same = 0;
        for (List<Integer> p : points) {
            int xi = p.get(0), yi = p.get(1);
            if (xi == x && yi == y) {
                ++same;
                continue;
            }
            v.add(Math.atan2(yi - y, xi - x));
        }
        Collections.sort(v);
        int n = v.size();
        for (int i = 0; i < n; ++i) {
            v.add(v.get(i) + 2 * Math.PI);
        }
        int mx = 0;
        Double t = angle * Math.PI / 180;
        for (int i = 0, j = 0; j < 2 * n; ++j) {
            while (i < j && v.get(j) - v.get(i) > t) {
                ++i;
            }
            mx = Math.max(mx, j - i + 1);
        }
        return mx + same;
    }
}
Step 06

Interactive Study Demo

Use this to step through a reusable interview workflow for this problem.

Press Step or Run All to begin.
Step 07

Complexity Analysis

Time
O(n)
Space
O(k)

Approach Breakdown

BRUTE FORCE
O(n × k) time
O(1) space

For each starting index, scan the next k elements to compute the window aggregate. There are n−k+1 starting positions, each requiring O(k) work, giving O(n × k) total. No extra space since we recompute from scratch each time.

SLIDING WINDOW
O(n) time
O(k) space

The window expands and contracts as we scan left to right. Each element enters the window at most once and leaves at most once, giving 2n total operations = O(n). Space depends on what we track inside the window (a hash map of at most k distinct elements, or O(1) for a fixed-size window).

Shortcut: Each element enters and exits the window once → O(n) amortized, regardless of window size.
Coach Notes

Common Mistakes

Review these before coding to avoid predictable interview regressions.

Off-by-one on range boundaries

Wrong move: Loop endpoints miss first/last candidate.

Usually fails on: Fails on minimal arrays and exact-boundary answers.

Fix: Re-derive loops from inclusive/exclusive ranges before coding.

Overflow in intermediate arithmetic

Wrong move: Temporary multiplications exceed integer bounds.

Usually fails on: Large inputs wrap around unexpectedly.

Fix: Use wider types, modular arithmetic, or rearranged operations.

Shrinking the window only once

Wrong move: Using `if` instead of `while` leaves the window invalid for multiple iterations.

Usually fails on: Over-limit windows stay invalid and produce wrong lengths/counts.

Fix: Shrink in a `while` loop until the invariant is valid again.

Related Problems
#1040Moving Stones Until Consecutive IImedium→#1248Count Number of Nice Subarraysmedium→#2110Number of Smooth Descent Periods of a Stockmedium→#3411Maximum Subarray With Equal Productseasy→#3505Minimum Operations to Make Elements Within K Subarrays Equalhard→