Is Convex Polygon easy or hard?

Convex Polygon is generally classified as a medium difficulty problem. The implementation is short, but it requires understanding geometric orientation and cross products. Candidates unfamiliar with computational geometry may find the reasoning step challenging.

How to solve Convex Polygon in O(n)?

Traverse the polygon and compute the cross product for every consecutive triple of vertices. Record the first non-zero cross product sign. Continue scanning and ensure every subsequent non-zero cross product has the same sign. If a sign flip occurs, the polygon is not convex.

What is the best approach for Convex Polygon?

The best approach is checking cross product sign consistency while iterating through consecutive triplets of vertices. Compute the orientation for each pair of adjacent edges and ensure all non-zero cross products have the same sign. This confirms the polygon always turns in the same direction, which guarantees convexity. The algorithm runs in O(n) time and O(1) space.

What data structure is used in Convex Polygon?

The input is typically stored in an array of coordinate pairs representing polygon vertices. The algorithm iterates through this array while performing geometric cross product calculations. No additional data structures are required beyond simple variables.

What is the time complexity of Convex Polygon?

The optimal solution runs in O(n) time because each vertex is processed once while evaluating cross products of consecutive edges. Space complexity is O(1) since only a few variables are used to track orientation signs. Brute force orientation checks can take up to O(n^3) time.

Convex Polygon Python or Java solution approach?

Both Python and Java implementations follow the same logic: iterate through points, compute cross products for three consecutive vertices, track the orientation sign, and ensure it never changes. The implementation uses basic arithmetic operations and a loop over the points array.

Is Convex Polygon asked at Google, Amazon, or Meta?

Convex polygon checks appear in interviews that test computational geometry fundamentals. Similar orientation and cross-product problems have been reported in interviews at companies like Google, Amazon, and Meta, especially for roles involving algorithmic problem solving.

Description Solution Video 14:11

469. Convex Polygon

Medium40.3% acceptance1 companyPremium elsewhere, free here

You are given an array of points on the X-Y plane points where points[i] = [x_i, y_i]. 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.

Example 1:

Input: points = [[0,0],[0,5],[5,5],[5,0]]
Output: true

Example 2:

Input: points = [[0,0],[0,10],[10,10],[10,0],[5,5]]
Output: false

Constraints:

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

Asked at 1 company

Google

Topics

14:11

Still stuck?Read the written solution, or watch a walkthrough.

Open solution

LanguageLoading editor…

1class Solution:
  def solve(self):
      pass


Starter codePython 3Spaces: 4

Examples

Case 1Case 2

Input

[[0,0],[0,5],[5,5],[5,0]]

Input

[[0,0],[0,10],[10,10],[10,0],[5,5]]

Your code is saved on this device.Solution