Maximum Number of Visible Points - Practice Coding Problems

Maximum Number of Visible Points - Problem

You are given an array points, an integer angle, and your location location = [posx, posy] where 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.

Input & Output

Example 1 — Basic Field of View

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

› Output: 3

💡 Note: With a 90° field of view, we can rotate to capture all 3 points. The optimal rotation direction allows us to see points at angles that fit within the 90° range.

Example 2 — Narrow View

$ Input: points = [[2,1],[2,2],[3,4],[1,1]], angle = 30, location = [1,1]

› Output: 2

💡 Note: Point [1,1] is at our location (always visible). With 30° field of view, we can see at most 1 additional point, for total of 2.

Example 3 — Wide View

$ Input: points = [[1,0],[2,1]], angle = 180, location = [1,1]

› Output: 2

💡 Note: With 180° field of view (half circle), we can see both points by rotating to an appropriate direction.

Constraints

1 ≤ points.length ≤ 10³
points[i].length == 2
location.length == 2
-10⁹ ≤ x_i, y_i ≤ 10⁹
0 ≤ angle < 360

Visualization

Tap to expand

Understanding the Visualization

Input Setup

Points scattered around your location with limited field of view

Rotate View

Find optimal rotation direction to maximize visible points

Count Maximum

Return the maximum number of points visible in any rotation

Key Takeaway

🎯 Key Insight: Convert geometric coordinates to angles and use sliding window to efficiently find optimal rotation

Asked in

G Google 12 f Facebook 8 a Amazon 6

The key insight is to convert the geometric problem into angles and use sliding window. Convert all points to polar angles from your location, sort them, then use a sliding window to efficiently find the rotation that captures the maximum points within the field of view. Best approach is sliding window with Time: O(n log n), Space: O(n).

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force - Try All Rotations	O(n²)	O(n)	Try every possible rotation angle and count visible points for each
Optimized Sliding Window	O(n log n)	O(n)	Sort angles and use sliding window to find maximum points in any angle range

Brute Force - Try All Rotations — Algorithm Steps

Calculate angle for each point relative to location
For each possible rotation direction (0 to 360°)
Count points within the field of view range
Return maximum count found

Visualization

Tap to expand

Step-by-Step Walkthrough

Calculate Angles

Convert all points to polar angles from location

Try Each Direction

For each angle, count points in field of view

Find Maximum

Return the rotation with most visible points

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>

int solution(int points[][2], int pointsSize, int angle, int location[]) {
    if (angle >= 360) {
        return pointsSize;
    }
    
    int sameLocation = 0;
    double angles[1000];
    int angleCount = 0;
    
    for (int i = 0; i < pointsSize; i++) {
        if (points[i][0] == location[0] && points[i][1] == location[1]) {
            sameLocation++;
        } else {
            double deg = atan2(points[i][1] - location[1], points[i][0] - location[0]) * 180.0 / M_PI;
            if (deg < 0) deg += 360;
            angles[angleCount++] = deg;
        }
    }
    
    if (angleCount == 0) {
        return sameLocation;
    }
    
    int maxPoints = sameLocation;
    
    for (int i = 0; i < angleCount; i++) {
        int count = sameLocation + 1;
        double startAngle = angles[i];
        
        for (int j = 0; j < angleCount; j++) {
            if (i != j) {
                double diff = fabs(angles[j] - startAngle);
                if (diff > 180) diff = 360 - diff;
                if (diff <= angle / 2.0) {
                    count++;
                }
            }
        }
        
        if (count > maxPoints) {
            maxPoints = count;
        }
    }
    
    return maxPoints;
}

int main() {
    // Simplified input parsing
    int points[100][2];
    int pointsSize = 0;
    int angle;
    int location[2];
    
    scanf("%d", &angle);
    
    printf("%d\n", solution(points, pointsSize, angle, location));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n²)

For each of n points as potential rotation center, we check all n points

⚠ Quadratic Growth

Space Complexity

O(n)

Store angles for all points

⚡ Linearithmic Space

28.4K Views

Medium Frequency

~25 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force - Try All Rotations — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler