Watch 4 video solutions for Convex Polygon, a medium level problem involving Array, Math, Geometry. This walkthrough by Programming Live with Larry has 258 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
You are given an array of points on the X-Y plane points where points[i] = [xi, yi]. The points form a polygon when joined sequentially.
Return true if this polygon is convex and false otherwise.
You may assume the polygon formed by given points is always a simple polygon. In other words, we ensure that exactly two edges intersect at each vertex and that edges otherwise don't intersect each other.
Example 1:
Input: points = [[0,0],[0,5],[5,5],[5,0]] Output: true
Example 2:
Input: points = [[0,0],[0,10],[10,10],[10,0],[5,5]] Output: false
Constraints:
3 <= points.length <= 104points[i].length == 2-104 <= xi, yi <= 104Problem Overview: You are given points of a polygon in order. The task is to determine whether the polygon is convex. A polygon is convex if every internal angle is less than 180°, which means the direction of turning between consecutive edges never changes sign.
Approach 1: Brute Force Orientation Check (O(n^3) time, O(1) space)
A direct but inefficient approach examines every combination of three vertices and checks the orientation using the cross product. For three points A, B, C, compute the cross product of vectors AB and BC. The sign tells whether the turn is clockwise or counterclockwise. If the polygon is convex, all triples formed from adjacent edges should maintain a consistent turning direction. The brute force variant redundantly recomputes orientations across many triples, leading to O(n^3) checks. It mainly helps build intuition about orientation and the geometric definition of convexity.
This approach relies heavily on basic math and geometry operations. However, repeated comparisons across many triplets make it impractical for larger inputs.
Approach 2: Cross Product Sign Consistency (O(n) time, O(1) space)
The optimal solution walks through the polygon once and checks the orientation of each consecutive triplet of vertices. For points A = points[i], B = points[(i+1) % n], and C = points[(i+2) % n], compute the cross product: (Bx - Ax) * (Cy - By) - (By - Ay) * (Cx - Bx). The sign indicates the direction of the turn. A convex polygon must turn either always clockwise or always counterclockwise as you traverse the edges.
During iteration, track the first non‑zero cross product sign. For each subsequent triplet, compute the cross product again and compare the sign. If any cross product has the opposite sign, the polygon has a reflex angle and is therefore not convex. Collinear points produce a cross product of zero and can simply be skipped. The modulo operation ensures the last vertices wrap around to the beginning of the polygon.
This single pass approach uses constant memory and performs only simple arithmetic operations on coordinates stored in an array. The key insight is that convexity depends only on consistent orientation of consecutive edges, not on global comparisons.
Recommended for interviews: The O(n) cross product sign consistency approach is the expected solution. Interviewers want to see that you understand orientation tests and can apply them while iterating around the polygon once. Mentioning the brute force orientation idea demonstrates geometric reasoning, but implementing the single-pass check shows you know how to translate that idea into an optimal algorithm.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Orientation Checks | O(n^3) | O(1) | Useful for understanding geometric orientation and validating convexity conceptually |
| Cross Product Sign Consistency (Single Pass) | O(n) | O(1) | Best general solution for checking convex polygons efficiently |