Insights -
- Moving the reference point to origin is a good simplification
- This is a sliding window, albeit an angular/ circular version
- We can evade a sort if we can cap the granularity (which we can still tune to suit space-accuracy balance)
Time Complexity - O(n) - n is number of points
Space Complexity - O(1) - 360/ 3600/ 36000… is still constant space as it is independent of any input.
One could make the case that the space complexity is O(1/k) where k = the angle between the 2 angularly closest points. Thoughts?
class Solution {
private int granularity = 1000; // 1/1000th of a degree
public int visiblePoints(List<List> points, int angle, List location) {
for (List<Integer> p : points)
{
p.set(0, p.get(0) - location.get(0));
p.set(1, p.get(1) - location.get(1));
}
int self = 0;
int[] startend = new int[360 * granularity];
int curr = 0;
for (List<Integer> p : points)
{
if (p.get(0) == 0 && p.get(1) == 0)
{
self++;
continue;
}
int subtends;
if (p.get(0) == 0)
subtends = (p.get(1) > 0 ? 90 : 270) * granularity;
else
subtends = (int)Math.round(Math.atan2(p.get(1), p.get(0)) * 180 * granularity / Math.PI);
int appears = Mod360(subtends - (granularity * angle/2));
int disappears = Mod360(subtends + 1 + (granularity * angle/2));
startend[appears] += 1;
startend[disappears] -= 1;
if (appears > disappears) curr++;
}
int mx = -1;
for (int a=0; a < 360 * granularity; a = (a+1))
{
curr = Math.max(0, curr+startend[a]);
mx = Math.max(mx, curr);
}
return mx + self;
}
private int Mod360(long angle)
{
if (angle < 0) return Mod360(angle+(360 * granularity));
if (angle >= (360 * granularity)) return Mod360(angle-(360 * granularity));
return (int)angle;
}
}