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 + 360 duplication 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 iterating 2n times 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 entirely.

🔓 The 2 problems in this chapter are free. Sign in with Google or Microsoft to start solving.

---

The one-line 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
angles = []
same = 0
for x, y in points:
    if [x, y] == location:
        same += 1                      # a point AT the viewer is always visible
        continue
    angles.append(math.degrees(math.atan2(y - location[1], x - location[0])))

angles.sort()
angles += [a + 360 for a in angles]    # linearise the wraparound

best = left = 0
for right in range(len(angles)):
    while angles[right] - angles[left] > angle:
        left += 1
    best = max(best, right - left + 1)
return best + same

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 — 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: comparing angles[right] - angles[left] > angle on values produced by atan2 can misjudge a point exactly on the boundary. Where the problem's tolerance matters, compare with a small epsilon.

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 — the values are then monotonic in the same direction as the input, and the comparison still picks the right end.

---

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 simulation. Field-of-view and line-of-sight queries — how many entities fall inside a cone from the player.
• Robotics. LIDAR and sensor sweeps, where readings are naturally angular and the zero crossing is a real source of bugs.
• Radar and surveillance. Counting contacts within a bearing window.
• Computational geometry. Angular sweeps underpin convex hull and visibility algorithms.
• Signal processing. Applying a quadratic response curve to sorted measurements and needing the result ordered.

---

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; count points at the viewer separately.
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.
Pattern: two-pointer fill by orientation. Target: O(n) time — better than the O(n log n) transform-then-sort.

---

6. Common pitfalls 🚫

• Using atan instead of atan2. 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.
• Sorting after the transform. Correct, and O(n log n) for a problem that is O(n).
• Handling a == 0 as a special case. Folding it in with a >= 0 works; 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

1. Change the axis. Points become angles; a parabola becomes distance from its vertex.
2. Duplicate to linearise a circle. + 360 here, 2n iterations elsewhere — the same idea.
3. atan2, always, for anything angular.
4. Handle the degenerate point — one located exactly at the viewer — outside the main loop.
5. A parabola's extremes are at the input's ends, which is what makes an outside-in fill correct.
6. Two pointers beat a sort whenever the output ordering can be derived rather than computed.
7. 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.