Senior LevelData Structures & Algorithms
How does Graham Scan compute the Convex Hull in O(N log N)?
ā Interview Prompt: Explain Convex Hull, Graham Scan algorithm using polar angle sorting and a stack, O(N log N) complexity, and applications.
The Convex Hull is the smallest convex polygon enclosing all given points.
Graham Scan: $O(N \log N)$
1
Find the bottom-most (then leftmost) point as the pivot.
2
Sort remaining points by polar angle with respect to the pivot.
3
Process points using a stack:
ā¢
Push first 3 points.
ā¢
For each new point: while the top-two stack points + new point make a clockwise (non-left) turn ā pop.
ā¢
Push the new point.
4
Stack contains convex hull vertices.
Code Implementation Example
typescript
type Point = [number, number];
function cross(O: Point, A: Point, B: Point): number {
return (A[0] - O[0]) * (B[1] - O[1]) - (A[1] - O[1]) * (B[0] - O[0]);
}
function convexHull(points: Point[]): Point[] {
const n = points.length;
if (n < 3) return points;
points.sort((a, b) => a[0] !== b[0] ? a[0] - b[0] : a[1] - b[1]);
const hull: Point[] = [];
// Lower hull
for (const p of points) {
while (hull.length >= 2 && cross(hull[hull.length-2], hull[hull.length-1], p) <= 0)
hull.pop();
hull.push(p);
}
// Upper hull
const lowerLen = hull.length + 1;
for (let i = n - 2; i >= 0; i--) {
while (hull.length >= lowerLen && cross(hull[hull.length-2], hull[hull.length-1], points[i]) <= 0)
hull.pop();
hull.push(points[i]);
}
return hull.slice(0, -1); // Andrew's monotone chain variant
}š”Andrew's Monotone Chain Convex Hull ā O(N log N) with clean stack logic.
šÆ Interview Key Takeaway
Convex Hull has many applications: collision detection, GIS mapping, computer vision. O(N log N) is optimal (bounded by sorting lower bound).
#DSA#Convex Hull#Computational Geometry#Senior
Back to all Data Structures & Algorithms Questionsā