LeetCode 469: Convex Polygon Solution

Master LeetCode problem 469 (Convex Polygon), a medium challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

469. Convex Polygon

Medium

Array Math Geometry

Problem Explanation

Explanation:

To determine if a given list of points forms a convex polygon, we can use the concept of the cross product of vectors. A polygon is convex if, for any three consecutive vertices of the polygon, the cross product of the two vectors formed by those vertices has the same sign (either positive or negative) for all consecutive triplets of vertices.

Algorithm:

Iterate through each triplet of points in the list.
Calculate the cross product of the vectors formed by the consecutive points.
Keep track of the sign of the cross product.
If the sign changes at any point, the polygon is not convex.
If the sign remains the same for all triplets, the polygon is convex.

Time complexity: O(n) Space complexity: O(1)

Solution Code

class Solution {
    public boolean isConvex(List<List<Integer>> points) {
        int n = points.size();
        boolean signChange = false;
        
        for (int i = 0; i < n; i++) {
            int x1 = points.get(i).get(0);
            int y1 = points.get(i).get(1);
            int x2 = points.get((i + 1) % n).get(0);
            int y2 = points.get((i + 1) % n).get(1);
            int x3 = points.get((i + 2) % n).get(0);
            int y3 = points.get((i + 2) % n).get(1);
            
            int crossProduct = (x2 - x1) * (y3 - y2) - (y2 - y1) * (x3 - x2);
            
            if (crossProduct != 0) {
                if (signChange && crossProduct > 0) {
                    return false;
                } else if (crossProduct < 0) {
                    signChange = true;
                }
            }
        }
        
        return true;
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 469 (Convex Polygon)?

This page provides optimized solutions for LeetCode problem 469 (Convex Polygon) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 469 (Convex Polygon)?

The time complexity for LeetCode 469 (Convex Polygon) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 469 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 469 in Java, C++, or Python.

Back to LeetCode Solutions