Convex Polygon - Practice Coding Problems

Convex Polygon - Problem

You are given an array of points on the X-Y plane points where points[i] = [xi, yi]. The points form a polygon when joined sequentially.

Return true if this polygon is convex and false otherwise.

You may assume the polygon formed by given points is always a simple polygon. In other words, we ensure that exactly two edges intersect at each vertex and that edges otherwise don't intersect each other.

Note: A polygon is convex if all interior angles are less than 180 degrees, which means all cross products of consecutive edge vectors have the same sign.

Input & Output

Example 1 — Square (Convex)

$ Input: points = [[0,0],[0,1],[1,1],[1,0]]

› Output: true

💡 Note: A square is convex. All interior angles are 90 degrees (less than 180), and all cross products have the same sign when traversed counterclockwise.

Example 2 — Concave Shape

$ Input: points = [[0,0],[0,10],[10,10],[10,0],[5,5]]

› Output: false

💡 Note: This forms a concave polygon with an inward dent. The interior angle at [5,5] is greater than 180 degrees, making it non-convex.

Example 3 — Triangle (Convex)

$ Input: points = [[0,0],[3,0],[1,2]]

› Output: true

💡 Note: Any triangle is always convex. All three interior angles are less than 180 degrees.

Constraints

3 ≤ points.length ≤ 10⁴
points[i].length == 2
-10⁴ ≤ x_i, y_i ≤ 10⁴
All the given points are unique

Visualization

Tap to expand

Understanding the Visualization

Input Points

Array of [x,y] coordinates forming a polygon

Cross Products

Calculate cross product for each consecutive triplet

Check Signs

All cross products must have consistent sign

Key Takeaway

🎯 Key Insight: A polygon is convex when all cross products have the same sign

Asked in

G Google 12 f Facebook 8 a Amazon 6

The key insight is that a polygon is convex if and only if all cross products of consecutive edge vectors have the same sign. The best approach uses cross product sign checking in a single pass. Time: O(n), Space: O(1).

Common Approaches

Approach	Time	Space	Notes
✓ Cross Product Sign Check	O(n)	O(1)	Calculate cross products of consecutive edges and check if all have same sign
Optimized Cross Product Check	O(n)	O(1)	Same algorithm but with early termination and overflow handling

Cross Product Sign Check — Algorithm Steps

Step 1: Iterate through all consecutive triplets of points
Step 2: Calculate cross product for each triplet
Step 3: Check if all cross products have consistent sign

Visualization

Tap to expand

Step-by-Step Walkthrough

Take 3 Points

Consider consecutive triplets of vertices

Calculate Cross Product

Find cross product of edge vectors

Check Sign Consistency

All cross products must have same sign

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

bool solution(int points[][2], int n) {
    if (n < 3) return true;
    
    int sign = 0;
    for (int i = 0; i < n; i++) {
        // Get three consecutive points (with wraparound)
        int *p1 = points[i];
        int *p2 = points[(i + 1) % n];
        int *p3 = points[(i + 2) % n];
        
        // Calculate cross product of vectors (p1->p2) and (p2->p3)
        int v1x = p2[0] - p1[0], v1y = p2[1] - p1[1];
        int v2x = p3[0] - p2[0], v2y = p3[1] - p2[1];
        long long cross = (long long)v1x * v2y - (long long)v1y * v2x;
        
        if (cross != 0) {
            if (sign == 0) {
                sign = cross > 0 ? 1 : -1;
            } else if ((cross > 0 && sign < 0) || (cross < 0 && sign > 0)) {
                return false;
            }
        }
    }
    
    return true;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    // Parse 2D array manually
    int points[1000][2];
    int n = 0;
    
    char *ptr = strchr(line, '[');
    while (ptr && *ptr) {
        if (*ptr == '[' && *(ptr+1) != '[') {
            sscanf(ptr, "[%d,%d]", &points[n][0], &points[n][1]);
            n++;
        }
        ptr++;
    }
    
    bool result = solution(points, n);
    printf(result ? "true\n" : "false\n");
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Single pass through all points to check each angle

✓ Linear Growth

Space Complexity

O(1)

Only using variables for calculations, no extra data structures

✓ Linear Space

28.0K Views

Medium Frequency

~25 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Cross Product Sign Check — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler