Domain 2MediumCORE

Convex Polygon

We are given a list of vertices representing a simple polygon in order. Our goal is to determine if this shape is convex. A polygon is convex if all its interior angles are less than or equal to 180 degrees, meaning no 'indentations' exist where the boundary turns inward relative to the traversal direction.

Domain: Medium•Updated: 2026-08-31
#Algorithms#LeetCode#qwen3.5:9b#Math

469. Convex Polygon

Model: qwen3.5:9b
Topics: Math
FAANG asked: 1
Acceptance rate: 37.6%


Problem Breakdown

We are given a list of vertices representing a simple polygon in order. Our goal is to determine if this shape is convex. A polygon is convex if all its interior angles are less than or equal to 180 degrees, meaning no “indentations” exist where the boundary turns inward relative to the traversal direction.

Inputs:

  • points: List of [x, y] coordinate pairs (integers).
  • Constraints: 3≤N≤10,0003 \le N \le 10,000, coordinates between -10,000 and 10,000. The polygon is guaranteed to be simple (no self-intersections), so we don’t need to validate topology or sort points; the input order defines the perimeter traversal.

Outputs:

  • True if convex, False otherwise.

Implicit Constraints & Edge Cases:

  • Wrap-around: Since it’s a polygon, the last point connects back to the first. We must handle index NN as index 0.
  • Collinear Points: Three consecutive points lying on a straight line result in a cross product of zero. Geometrically, this is still considered convex (an angle of exactly 180 degrees). However, we only care if signs flip from positive to negative or vice versa; zeros are neutral and do not break convexity unless they sandwich non-zero turns with different directions.
  • Overflow: With coordinates up to 10410^4, the cross product can reach roughly (2⋅104)2=4⋅108(2 \cdot 10^4)^2 = 4 \cdot 10^8. This fits comfortably within a standard 32-bit integer, and Python handles arbitrary precision integers automatically anyway.

Intuition

A brute-force approach might try to calculate every interior angle using trigonometry (atan2) or check if the diagonal between non-adjacent vertices lies inside the polygon. Calculating angles is computationally expensive (O(N)O(N) with potential floating-point errors), and checking diagonals for all pairs becomes O(N3)O(N^3), which is too slow given N=10,000N=10,000.

The key insight relies on vector geometry: When traversing a convex polygon boundary in order (clockwise or counter-clockwise), the “turn” at every vertex must be consistent. You either always turn left or always turn right. If you ever switch from turning left to turning right (or vice versa) without passing through 180 degrees, there is an indentation (concavity).

We can determine the direction of a turn using the 2D Cross Product of two consecutive edge vectors:

  • Let u⃗=Pi+1−Pi\vec{u} = P_{i+1} - P_i and v⃗=Pi+2−Pi+1\vec{v} = P_{i+2} - P_{i+1}.
  • The cross product CP=uxvy−uyvxCP = u_x v_y - u_y v_x.
  • If CP>0CP > 0, it’s a left turn.
  • If CP<0CP < 0, it’s a right turn.
  • If CP==0CP == 0, points are collinear (straight line).

For the polygon to be convex, all non-zero cross products must share the same sign. We iterate through every vertex and check this condition.

Approach

  1. Initialize a variable sign to track the direction of turns encountered so far. Since we don’t know if it’s clockwise or counter-clockwise yet, we can set an initial state based on the first valid turn (or handle zeros carefully). A robust way is to iterate and update prev_sign.
  2. Iterate through each vertex ii from 0 to N−1N-1. We need three consecutive points: current (PiP_i), next (PnextP_{next}), and after-next (Pafter_nextP_{after\_next}). Since the polygon wraps around, indices are calculated modulo NN.
  3. Compute vectors u⃗=Pi+1−Pi\vec{u} = P_{i+1} - P_i and v⃗=Pi+2−Pi+1\vec{v} = P_{i+2} - P_{i+1}.
  4. Calculate cross product: cp = u_x * v_y - u_y * v_x.
  5. Determine the sign of this cross product (positive, negative, or zero).
  6. If we encounter a non-zero value and it differs from our previously recorded turn direction (prev_sign), return False.
  7. Update prev_sign to match current if valid. Handle zeros by ignoring them for sign comparison but updating the state only when a definitive left/right turn occurs (or simply track that all previous were 0). A simpler logic: store the first non-zero cross product’s sign as reference, then compare subsequent ones against it.
  8. If loop completes without returning False, return True.

Complexity Analysis

  • Time Complexity: O(N)O(N) where NN is the number of points. We iterate through the list exactly once performing constant-time arithmetic operations per vertex.
  • Space Complexity: O(1)O(1). We only store a few variables for coordinates and cross product results; we do not need extra data structures proportional to input size (no sorting or recursion).

Solution

def isConvexPolygon(points):
    n = len(points)
    
    # Helper lambda to get vector components between two points
    def vec(p1, p2):
        return [p2[0] - p1[0], p2[1] - p1[1]]

    prev_sign = 0
    
    for i in range(n):
        # Indices wrap around using modulo n
        curr_idx = (i + 1) % n
        next_idx = (i + 2) % n
        
        u_x, u_y = points[curr_idx][0] - points[i][0], \
                   points[curr_idx][1] - points[i][1]
        
        v_x, v_y = points[next_idx][0] - points[curr_idx][0], \
                   points[next_idx][1] - points[curr_idx][1]
                   
        # Cross product of vectors u and v: (u x v) in 2D is scalar z-component
        cross_product = u_x * v_y - u_y * v_x
        
        current_sign = cross_product if cross_product != 0 else 0
        
        # If we have a definitive turn direction established, check consistency.
        # Note: We must ensure prev_sign isn't still the initial 'neutral' state 
        # before comparing against zeros to avoid false negatives on straight edges.
        
        if current_sign == 0:
            continue
            
        if prev_sign != 0 and (current_sign > 0) != (prev_sign > 0):
            return False
        
        prev_sign = current_sign

    return True

Edge Cases Handled

  • Collinear Vertices: If three consecutive points are collinear, the cross product is zero. The code skips updating prev_sign or comparing signs when it’s zero, effectively treating straight edges as valid convex continuations rather than concavities.
  • Wrap-around Logic: Using (i + 1) % n and (i + 2) % n ensures the last vertex connects correctly to the first two vertices in a circular buffer manner without needing explicit boundary checks inside the loop logic.
  • Negative Coordinates: The cross product formula relies on differences, so negative coordinates are handled naturally by standard integer arithmetic (Python handles large integers automatically).
  • Minimum Points (N=3N=3): The loop runs correctly for N≥3N \ge 3. With exactly 3 points forming a triangle, the logic holds as long as they don’t overlap or form a straight line.