Solution videos are here - Watch walkthroughs for selected problems. Check them out

⚡ Build the skills to land top-paying quant jobs. Offer ends in 17d 22h 18m 43s17 days 22 hours 18 minutes 43 seconds.

Advanced - Geometry · 4:16

Convex Hull: Graham Scan & Monotone Chain

The convex hull is the smallest convex polygon containing a point set. Graham's scan takes the lowest point P0, sorts the rest by angle with cross products and keeps a stack that pops every point where the chain fails to turn left; Andrew's monotone chain gets the same hull from a plain (x, y) sort with a lower and an upper pass. Both cost O(n log n) for the sort plus O(n) for the stack, and the pop condition (≤ 0 or < 0) decides whether points on hull edges are kept, with all-collinear inputs handled separately.

You will learn

Run Graham's scan: choose P0, sort by orientation around it, and maintain the hull on a stack with the turn test
Build the same hull with Andrew's monotone chain from a lexicographic sort and two passes
Explain the O(n log n) cost and the amortised O(n) stack (every point pushed once and popped at most once)
Choose the pop condition to include or exclude collinear boundary points and handle duplicates and all-collinear inputs

Chapters

PreviousPolygon Area, Pick's Theorem & Lattice Points NextManhattan Distance Tricks