Convex Polygon - Solution & Explanation

Problem 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.