Angular and Two-Pointer
What is this?
Both problems here are easy once you stop looking at the data you were given and look at a different axis. Points scattered on a plane become a one-dimensional list of angles. A quadratic applied to a sorted array is not sorted, but it is monotonic outward from its vertex, which means the extremes sit at the two ends and can be collected inward.
Neither needs a clever data structure. Both need you to notice which ordering already exists.
Fun fact: the
+ 360duplication is the angular version of a trick that appears throughout the curriculum: linearise a circular problem by writing the data twice. It is the same move that makes circular next-greater-element work by iterating2ntimes with% n, and the same reason a doubled string contains every rotation of itself. Whenever wraparound is the only complication, duplicating the sequence usually removes it.
🔓 The 2 problems in this chapter are free. Sign in with Google or Microsoft to start solving.
Core idea: find the axis on which the data is already ordered (the angle from the viewer, or the distance from a parabola's vertex) and a standard linear technique applies without any new machinery.
1. Points become angles
import math
EPS = 1e-9 # degrees: absorbs float noise on exact ties
lx, ly = location
angles = []
same = 0
for x, y in points:
if x == lx and y == ly:
same += 1 # a point AT the viewer is always visible
continue
angles.append(math.degrees(math.atan2(y - ly, x - lx)))
angles.sort()
n = len(angles)
extended = angles + [a + 360 for a in angles] # linearise the wraparound
best = left = 0
for right in range(len(extended)):
while extended[right] - extended[left] > angle + EPS:
left += 1
best = max(best, right - left + 1)
return min(best, n) + same # min: at angle 360 a bearing and its copy both fit
Three details decide correctness. atan2 handles all four quadrants and the vertical case, where a naive atan(y/x) divides by zero. Points located exactly at the viewer have no defined angle and are visible regardless, so count them separately and add at the end. And the duplication must happen after sorting, so the appended copies stay in order.
Floating point deserves a word: two bearings exactly angle apart can come out as angle + 1e-14 after atan2, and a strict > then drops a visible point. Compare against angle + 1e-9. The min(best, n) clamp matters only at angle == 360, where a bearing and its own + 360 copy would otherwise both be counted.
2. A parabola is monotonic from its ends
Applying f(x) = ax² + bx + c to a sorted array does not give a sorted result, but the shape is predictable. When a > 0 the parabola opens upward, so the largest values are at the two ends of the input and the smallest is somewhere in the middle. When a < 0 it is the reverse.
So fill the output from the outside in:
res = [0] * len(nums)
i, j = 0, len(nums) - 1
write = len(nums) - 1 if a >= 0 else 0
step = -1 if a >= 0 else 1
while i <= j:
fi, fj = f(nums[i]), f(nums[j])
if (a >= 0) == (fi > fj): # take whichever end wins for this orientation
res[write] = fi; i += 1
else:
res[write] = fj; j -= 1
write += step
return res
a == 0 makes it linear, and folding it in with a >= 0 handles it correctly. A line is monotonic (increasing or decreasing), so its largest value is still at one of the two ends, and the comparison picks the right one.
3. A 30-second worked example (the wrap)
Angles at 350° and 10°, with a field of view of 30°. On the raw sorted list [10, 350] the gap reads as 340° and the window sees one point.
The two points are 20° apart across the zero mark, and the duplication is what lets a left-to-right window see it. Without it, no window over [10, 350] ever contains both.
4. Where you'll actually meet this
- Games and graphics. Field-of-view tests: which entities fall inside a cone from the viewer.
- Sensors. A sensor with a fixed aperture and a free heading, where readings are naturally angular and the zero crossing is a classic source of bugs.
- Computational geometry. Sorting points by angle around a center is the first step of Graham scan for convex hulls.
- Sorted data through a transform. Keeping a column ordered after a quadratic calibration, without paying for a re-sort.
5. Problems in this chapter
Maximum Number of Visible Points
Most points visible within a fixed angular field of view. Convert to angles with atan2, sort, append every angle + 360, then run an ordinary window with a 1e-9 tolerance; count points at the viewer separately and clamp the windowed count to the number of directional points.
Pattern: angular window with wraparound duplication. Target: O(n log n) time, O(n) space.
Sort Transformed Array
Apply ax² + bx + c to a sorted array and return the sorted result. Two pointers fill outside-in, because a parabola is monotonic outward from its vertex. In Java or C++ do the arithmetic in long: with |a|, |x| up to 10^4, a*x*x reaches 10^12.
Pattern: two-pointer fill by orientation. Target: O(n) time and O(n) output space, better than the O(n log n) transform-then-sort.
6. Common pitfalls
- Using
ataninstead ofatan2. It loses the quadrant and divides by zero on vertical alignments. - Forgetting points at the viewer. They have no angle, are always visible, and must be added after the window.
- Duplicating before sorting. The appended copies must preserve order or the window breaks.
- Ignoring floating-point tolerance on points exactly at the field-of-view boundary. Compare against
angle + 1e-9. - Forgetting the clamp at
angle == 360. A bearing and its+ 360copy both fit in the window, so cap the count at the number of directional points. - Sorting after the transform. Correct, and
O(n log n)for a problem that isO(n). - Handling
a == 0as a special case. Folding it in witha >= 0works, even for a decreasing line; a separate branch is easy to get backwards. - Writing the output forwards when
a > 0. The largest values come first, so the write pointer must start at the end and move backwards.
7. Key takeaways
- Change the axis. Points become angles; a parabola becomes distance from its vertex.
- Duplicate to linearise a circle.
+ 360here,2niterations elsewhere: the same idea. atan2, always, for anything angular.- Handle the degenerate point, one located exactly at the viewer, outside the main loop. Add a small epsilon to the window test and clamp at
angle == 360. - A parabola's extremes are at the input's ends, which is what makes an outside-in fill correct.
- Two pointers beat a sort whenever the output ordering can be derived rather than computed.
- Why interviewers like it: both problems look geometric and are solved by ordinary linear techniques once the right ordering is spotted. That spotting is the whole test.
Order: Maximum Number of Visible Points → Sort Transformed Array.
Sort Transformed Array
Core idea:
numsis already sorted and you apply a quadraticf(x) = ax² + bx + cto every element. Mapping and callingsort()costsO(n log n), but a parabola is monotone on each side of its vertex, so for any sorted window the largest value off(whena > 0) or the smallest (whena < 0) is at one of the two ends. Put a pointer at each end. Ifa >= 0, comparef(left)andf(right), take the larger and write it into the result from the back. Ifa < 0, take the smaller and write from the front. Each step consumes one end, so the whole thing isO(n). The fill direction is the only part people get wrong.
Sign in to continue reading
The rest of this lesson is available with a free account. Signing in with Google or Microsoft is free.
Sign in to read the full lesson