LeetCode 469 - Convex Polygon

The problem gives us a sequence of points on a 2D plane. These points are connected in order, and the final point connects back to the first point, forming a polygon. Our task is to determine whether that polygon is convex.

leetcodemediumarraymathgeometry

LeetCode Problem 469

Difficulty: 🟡 Medium
Topics: Array, Math, Geometry

Solution

Problem Understanding

The problem gives us a sequence of points on a 2D plane. These points are connected in order, and the final point connects back to the first point, forming a polygon. Our task is to determine whether that polygon is convex.

A polygon is convex if every internal angle is less than 180 degrees. Another equivalent geometric property is that while traversing the polygon in order, every turn must happen in the same direction. In other words, the polygon must consistently turn either clockwise or counterclockwise.

For example, a square is convex because every corner bends in the same direction. However, a polygon with an inward dent is not convex because at least one corner bends the opposite way.

The input is an array points, where each element contains the coordinates [x, y] of a vertex. The vertices are already given in traversal order, either clockwise or counterclockwise. The problem guarantees that the polygon is simple, meaning edges only meet at adjacent vertices and do not cross each other elsewhere. This guarantee is important because self intersecting polygons would require additional geometric handling.

The constraints allow up to 10^4 points, which means the solution must be efficient. An O(n) or O(n log n) solution is acceptable, but an O(n^2) or worse approach may become too slow.

Several edge cases are important:

  • Collinear consecutive points can produce a cross product of zero.
  • The polygon may be provided in clockwise or counterclockwise order.
  • Negative coordinates are allowed.
  • The polygon may contain a single inward bend that invalidates convexity.
  • Since the polygon is guaranteed to be simple, we do not need to check for edge intersections.

Approaches

Brute Force Approach

A straightforward way to determine whether a polygon is convex is to compute every internal angle explicitly. For each vertex, we can form vectors using its neighboring vertices and compute the angle between them using dot products or trigonometric functions.

If every internal angle is strictly less than 180 degrees, then the polygon is convex.

This approach is correct because convexity is directly defined in terms of internal angles. However, angle computations involve floating point arithmetic, inverse cosine operations, and careful handling of precision issues. Additionally, explicitly computing angles is more complicated than necessary.

A more exhaustive brute force interpretation would also check whether every diagonal lies completely inside the polygon, which leads to much higher complexity.

While feasible for the given constraints, these methods are unnecessarily expensive and error prone.

Optimal Approach

The key geometric insight is that convex polygons always turn in the same direction while traversing their vertices.

We can detect turning direction using the 2D cross product.

Given three consecutive points A, B, and C, we form two vectors:

  • AB = B - A
  • BC = C - B

The sign of the cross product tells us the turning direction:

  • Positive cross product means counterclockwise turn
  • Negative cross product means clockwise turn
  • Zero means collinear points

For a convex polygon, all nonzero cross products must have the same sign.

This allows us to solve the problem in a single pass through the vertices.

Approach Time Complexity Space Complexity Notes
Brute Force O(n) O(1) Computes internal angles explicitly using geometry formulas
Optimal O(n) O(1) Uses cross product sign consistency to detect convexity

Algorithm Walkthrough

  1. Iterate through every vertex of the polygon.

Since the polygon is cyclic, each vertex needs both its previous and next neighbors. We use modular arithmetic so that the last point connects back to the first point naturally. 2. For each triplet of consecutive points (A, B, C), compute the cross product.

The formula is:

$(B_x-A_x)(C_y-B_y)-(B_y-A_y)(C_x-B_x)$

This value determines whether the turn at vertex B is clockwise or counterclockwise. 3. Ignore zero cross products.

A zero cross product means the three points are collinear. Collinear edges do not affect convexity, so we skip them. 4. Store the sign of the first nonzero cross product.

This establishes the expected turning direction for the entire polygon. 5. Continue checking all remaining cross products.

If any later nonzero cross product has the opposite sign, then the polygon changes turning direction and therefore cannot be convex. 6. If the entire traversal finishes without contradiction, return true.

This means all turns were consistent.

Why it works

A simple polygon is convex if and only if every boundary turn occurs in the same rotational direction. The cross product precisely captures this directional turn information. Because the polygon is guaranteed to be simple, any change in turn direction necessarily creates an inward indentation, which makes the polygon non convex. Therefore, consistent cross product signs are both necessary and sufficient for convexity.

Python Solution

from typing import List

class Solution:
    def isConvex(self, points: List[List[int]]) -> bool:
        n = len(points)
        previous_cross = 0

        for i in range(n):
            x1, y1 = points[i]
            x2, y2 = points[(i + 1) % n]
            x3, y3 = points[(i + 2) % n]

            dx1 = x2 - x1
            dy1 = y2 - y1
            dx2 = x3 - x2
            dy2 = y3 - y2

            cross = dx1 * dy2 - dy1 * dx2

            if cross != 0:
                if previous_cross != 0 and cross * previous_cross < 0:
                    return False

                previous_cross = cross

        return True

The implementation follows the geometric observation directly.

The variable previous_cross stores the sign of the first meaningful turn. During iteration, we continuously compute the cross product for each set of three consecutive points.

The modulo operator allows the polygon traversal to wrap around naturally, which avoids special handling for the final vertices.

When the cross product is zero, the points are collinear, so the algorithm ignores that turn and continues.

The condition:

cross * previous_cross < 0

detects a sign change. If this occurs, the polygon changes turning direction, so the function immediately returns False.

If the loop completes successfully, every turn was consistent and the polygon is convex.

Go Solution

func isConvex(points [][]int) bool {
	n := len(points)
	prevCross := 0

	for i := 0; i < n; i++ {
		x1, y1 := points[i][0], points[i][1]
		x2, y2 := points[(i+1)%n][0], points[(i+1)%n][1]
		x3, y3 := points[(i+2)%n][0], points[(i+2)%n][1]

		dx1 := x2 - x1
		dy1 := y2 - y1
		dx2 := x3 - x2
		dy2 := y3 - y2

		cross := dx1*dy2 - dy1*dx2

		if cross != 0 {
			if prevCross != 0 && cross*prevCross < 0 {
				return false
			}

			prevCross = cross
		}
	}

	return true
}

The Go implementation is nearly identical to the Python version. Since Go uses fixed width integers, it is worth considering overflow. However, the coordinate constraints are only 10^4, so the cross product remains safely within the 32 bit integer range.

Go slices are used naturally for the input structure. No additional memory allocation is required beyond a few integer variables.

Worked Examples

Example 1

points = [[0,0],[0,5],[5,5],[5,0]]

This forms a square.

i A B C Cross Product Direction
0 (0,0) (0,5) (5,5) -25 Clockwise
1 (0,5) (5,5) (5,0) -25 Clockwise
2 (5,5) (5,0) (0,0) -25 Clockwise
3 (5,0) (0,0) (0,5) -25 Clockwise

Every cross product has the same sign, so the polygon is convex.

Result:

true

Example 2

points = [[0,0],[0,10],[10,10],[10,0],[5,5]]

This polygon contains an inward dent.

i A B C Cross Product Direction
0 (0,0) (0,10) (10,10) -100 Clockwise
1 (0,10) (10,10) (10,0) -100 Clockwise
2 (10,10) (10,0) (5,5) -50 Clockwise
3 (10,0) (5,5) (0,0) 50 Counterclockwise

At index 3, the turning direction changes sign.

That means the polygon is not convex.

Result:

false

Complexity Analysis

Measure Complexity Explanation
Time O(n) Each vertex is processed exactly once
Space O(1) Only a few variables are used regardless of input size

The algorithm performs a single traversal of the polygon and computes constant time geometric operations for each vertex. No auxiliary data structures are required, so the memory usage remains constant.

Test Cases

from typing import List

class Solution:
    def isConvex(self, points: List[List[int]]) -> bool:
        n = len(points)
        previous_cross = 0

        for i in range(n):
            x1, y1 = points[i]
            x2, y2 = points[(i + 1) % n]
            x3, y3 = points[(i + 2) % n]

            dx1 = x2 - x1
            dy1 = y2 - y1
            dx2 = x3 - x2
            dy2 = y3 - y2

            cross = dx1 * dy2 - dy1 * dx2

            if cross != 0:
                if previous_cross != 0 and cross * previous_cross < 0:
                    return False

                previous_cross = cross

        return True

sol = Solution()

assert sol.isConvex([[0,0],[0,5],[5,5],[5,0]]) == True  # basic square
assert sol.isConvex([[0,0],[0,10],[10,10],[10,0],[5,5]]) == False  # inward dent
assert sol.isConvex([[0,0],[1,1],[2,0]]) == True  # simple triangle
assert sol.isConvex([[0,0],[2,0],[2,2],[1,1],[0,2]]) == False  # concave pentagon
assert sol.isConvex([[0,0],[1,0],[2,0],[2,2],[0,2]]) == True  # collinear points
assert sol.isConvex([[-1,-1],[1,-1],[1,1],[-1,1]]) == True  # negative coordinates
assert sol.isConvex([[0,0],[4,0],[4,4],[2,1],[0,4]]) == False  # inward notch
assert sol.isConvex([[0,0],[3,0],[5,2],[3,5],[0,5],[-2,2]]) == True  # convex hexagon
Test Why
Square Basic convex polygon
Polygon with inward dent Standard concave example
Triangle Smallest valid polygon
Concave pentagon Detects sign change
Collinear edge points Ensures zero cross products are handled
Negative coordinates Confirms coordinate sign does not matter
Inward notch Tests subtle concavity
Convex hexagon Larger convex shape

Edge Cases

Collinear Consecutive Points

A polygon may contain consecutive points lying on the same straight line. In this situation, the cross product becomes zero.

A naive implementation might incorrectly treat zero as a direction change. This implementation explicitly ignores zero cross products, which correctly preserves convexity behavior.

Clockwise Versus Counterclockwise Ordering

The polygon vertices may be provided in either traversal direction.

Some incorrect solutions assume the polygon must always produce positive cross products. In reality, a valid convex polygon can produce either all positive or all negative cross products depending on orientation.

This implementation only checks consistency of sign, not the specific sign itself.

Concavity Appearing Late in the Traversal

A polygon may appear convex for most vertices and only contain a single inward bend near the end.

An incomplete implementation that stops early could miss this case. The algorithm checks every vertex in cyclic order, ensuring even late sign changes are detected correctly.