LeetCode 469: Convex Polygon Solution in Python – A Step-by-Step Guide

What Is LeetCode 469: Convex Polygon?

In LeetCode 469: Convex Polygon, you’re given a list of 2D points as points (e.g., [[x1,y1], [x2,y2], ...]), representing vertices in order (clockwise or counterclockwise). Your task is to return True if they form a convex polygon—no dents (concave angles > 180°) and no three consecutive points collinear—or False otherwise. For example, [[1,1], [2,2], [3,3], [4,4]] is not convex (straight line), but [[1,0], [2,2], [2,0]] is convex (triangle). It’s like checking if a shape’s outline stays “bulged out” without caving in.

Problem Statement

• Input: points (List[List[int]])—list of [x, y] coordinates in order.
• Output: bool—True if convex, False otherwise.
• Rules:
• Points form a polygon in given order.
• Convex: All interior angles < 180°, no three points collinear.
• At least 3 points.

Constraints

• 3 <= points.length <= 10^4.
• -10^4 <= points[i][0], points[i][1] <= 10^4.

Examples to Get Us Started

• Input: points = [[1,1],[2,2],[2,0],[1,0]]
• Output: True (Convex square).
• Input: points = [[1,1],[2,2],[3,3]]
• Output: False (Collinear).
• Input: points = [[0,0],[0,1],[1,1],[1,0],[0,0]]
• Output: True (Square, repeated start ignored).

Understanding the Problem: Mapping the Shape

To solve LeetCode 469: Convex Polygon in Python, we need to verify if a polygon is convex by ensuring all turns are in the same direction (e.g., all left or all right) and no three points lie on a straight line. A naive approach—computing all angles—could be O(n) but complex. The key? Use the cross product to check turn directions efficiently. We’ll explore:

• Best Solution (Cross-Product Direction Checking): O(n) time, O(1) space—fast and optimal.
• Alternative Solution (Brute Force Angle Checking): O(n) time, O(1) space—intuitive but cumbersome.

Let’s dive into the cross-product solution—it’s the surveyor’s precise compass we need.

Best Solution: Cross-Product Direction Checking

Why This Is the Best Solution

The cross-product direction checking approach is the top pick because it’s O(n) time and O(1) space, efficiently determining convexity by checking the sign of cross products for consecutive triplets of points. A convex polygon requires all turns to be in the same direction (positive or negative cross products), with no zeros (collinearity). It’s like tracing the outline with a compass, ensuring every turn bends the same way—elegant and swift!

How It Works

Here’s the strategy:

• Step 1: Define cross product for vectors (p1, p2, p3):
• Vector v1 = p2 - p1, v2 = p3 - p2.
• Cross = v1.x * v2.y - v1.y * v2.x.
• Step 2: Iterate triplets (i, i+1, i+2 % n):
• Compute cross product.
• Track first non-zero sign, ensure all match.
• If zero (collinear), return False.
• Step 3: Return True if consistent, False otherwise.
• Why It Works:
• Cross product sign indicates turn direction (left > 0, right < 0).
• Consistency = convexity, zero = collinearity.

Step-by-Step Example

Example: points = [[1,1], [2,2], [2,0], [1,0]]

• Triplets:
• (1,1), (2,2), (2,0):
• v1 = [1,1], v2 = [0,-2].
• Cross = 1*-2 - 1*0 = -2 (right).
• (2,2), (2,0), (1,0):
• v1 = [0,-2], v2 = [-1,0].
• Cross = 0*0 - (-2)*-1 = -2 (right).
• (2,0), (1,0), (1,1):
• v1 = [-1,0], v2 = [0,1].
• Cross = -1*1 - 0*0 = -1 (right).
• (1,0), (1,1), (2,2):
• v1 = [0,1], v2 = [1,1].
• Cross = 0*1 - 1*1 = -1 (right).
• All negative: Convex, True.

Example: points = [[1,1], [2,2], [3,3]]

• Cross: [1,1], [1,1] → 0 (collinear).
• Result: False.

Code with Detailed Line-by-Line Explanation

Here’s the Python code, broken down clearly:

Copy codeclass Solution:
    def isConvex(self, points: List[List[int]]) -> bool:
        n = len(points)
        if n < 3:
            return False

        # Cross product helper
        def cross_product(p1, p2, p3):
            x1, y1 = p2[0] - p1[0], p2[1] - p1[1]
            x2, y2 = p3[0] - p2[0], p3[1] - p2[1]
            return x1 * y2 - y1 * x2

        # Step 2: Check all triplets
        prev_sign = 0
        for i in range(n):
            p1 = points[i]
            p2 = points[(i + 1) % n]
            p3 = points[(i + 2) % n]
            curr = cross_product(p1, p2, p3)

            if curr == 0:  # Collinear
                return False
            sign = 1 if curr > 0 else -1
            if prev_sign == 0:
                prev_sign = sign
            elif sign != prev_sign:
                return False

        return True

• Line 4-5: Early exit for < 3 points.
• Line 8-11: Cross product: computes turn direction.
• Line 14-25: Iterate triplets:
• Get p1, p2, p3 with modulo for wraparound.
• Compute cross, check collinearity (0).
• Track sign consistency.
• Line 27: Return True if convex.
• Time Complexity: O(n)—single pass.
• Space Complexity: O(1)—few variables.

It’s like a geometric turn tracker!

Alternative Solution: Brute Force Angle Checking

Why an Alternative Approach?

The brute force angle checking computes interior angles—O(n) time, O(1) space—using trigonometry or dot products, checking if all are < 180° and no collinearity. It’s intuitive but complex, like measuring every corner with a protractor. Good for clarity or small n!

How It Works

• Step 1: Compute vectors for each triplet.
• Step 2: Calculate angles via dot product.
• Step 3: Check all < 180°, no 0° or 180°.

Step-by-Step Example

Example: points = [[1,1], [2,2], [2,0]]

• Angles (simplified):
• (1,1)→(2,2)→(2,0): ~90°.
• (2,2)→(2,0)→(1,1): ~90°.
• (2,0)→(1,1)→(2,2): ~45°.
• All < 180°, no 0°/180°: True.

Code for Brute Force

Copy codeclass Solution:
    def isConvex(self, points: List[List[int]]) -> bool:
        n = len(points)
        if n < 3:
            return False

        def angle_sign(p1, p2, p3):
            x1, y1 = p2[0] - p1[0], p2[1] - p1[1]
            x2, y2 = p3[0] - p2[0], p3[1] - p2[1]
            cross = x1 * y2 - y1 * x2
            return 1 if cross > 0 else -1 if cross < 0 else 0

        prev_sign = 0
        for i in range(n):
            sign = angle_sign(points[i], points[(i + 1) % n], points[(i + 2) % n])
            if sign == 0:
                return False
            if prev_sign == 0:
                prev_sign = sign
            elif sign != prev_sign:
                return False
        return True

• Time Complexity: O(n)—angle checks.
• Space Complexity: O(1)—minimal space.

It’s a slow protractor!

Comparing the Two Solutions

• Cross-Product (Best):
• Pros: O(n), O(1), clear logic.
• Cons: Geometry knowledge needed.
• Angle Checking (Alternative):
• Pros: O(n), O(1), intuitive.
• Cons: More math complexity.

Cross-product wins for simplicity.

Edge Cases and Examples

• Input: [[1,1],[2,2]] → False.
• Input: [[1,1],[1,1],[2,2]] → False (duplicate).
• Input: [[0,0],[1,1],[0,1]] → True.

Cross-product handles all well.

Complexity Recap

• Cross-Product: Time O(n), Space O(1).
• Angle Checking: Time O(n), Space O(1).

Cross-product’s the champ.

Key Takeaways

• Cross-Product: Direction rules.
• Angle Checking: Measure carefully.
• Python Tip: Geometry simplifies—see [Python Basics](/python/basics).

Final Thoughts: Plot That Polygon

LeetCode 469: Convex Polygon in Python is a geometric mapping quest. Cross-product checking is your fast compass, while angle checking is a steady protractor. Want more geometry? Try LeetCode 587: Erect the Fence or LeetCode 149: Max Points on a Line. Ready to survey some shapes? Head to Solve LeetCode 469 on LeetCode (if unlocked) and plot it today—your coding skills are shape-ready!