Convex Polygon (LeetCode 469)
You will see how the sign of one integer per corner tells whether a polygon has a dent.
points lists the corners of a polygon in the order you meet them when you walk along its edge: each point is joined to the next one, and the last point is joined back to the first. The polygon is guaranteed to be simple: every corner touches exactly two edges, and no two edges meet or cross anywhere else.
Return true if the polygon is convex and false if it is not. A convex polygon has no dent: walking around it, you always turn the same way (only left turns, or only right turns). Three corners in a row may lie on one straight line; such a straight corner is not a turn, so it never makes the polygon non-convex.
Worked Examples
points = [[0,0],[0,5],[5,5],[5,0]]truepoints = [[0,0],[0,10],[10,10],[10,0],[5,5]]false⚖️Formal Constraints & Bounds
3 <= points.length <= 104points[i].length == 2-104 <= xi, yi <= 104All the given points are unique.
Why It Works & Core Invariant
One integer, cross(o, a, b), says whether the edge turns left or right at a corner. A polygon is convex exactly when every non-zero turn has the same sign, and a turn of 0 (a straight corner) changes nothing.
Real-World Scenario & Production Applications
A map or CAD tool checking that a drawn outline (a building footprint, a delivery zone, a collision shape in a game) has no dent before handing it to an algorithm that only works on convex shapes, such as a fast point-in-polygon test or a separating-axis collision check.
Subproblems & Recurrence Decomposition3 Phases
Establish 4-wall perimeter bounding (top, bottom, left, right) or binary exponent halving state x^n = (x^2)^(n/2).
top, bottom = 0, R - 1
left, right = 0, C - 1
res = []Step-by-Step Execution Trace Table
Example 2, points = [[0,0],[0,10],[10,10],[10,0],[5,5]] (n = 5):
| Step | i | Corner points[(i + 1) % n] | turn | prev before | Result |
|---|---|---|---|---|---|
| 1 | 0 | (0,10) | cross((0,0), (0,10), (10,10)) = -100 | 0 | first turn: prev = -100 (right) |
| 2 | 1 | (10,10) | cross((0,10), (10,10), (10,0)) = -100 | -100 | same sign: prev = -100 |
| 3 | 2 | (10,0) | cross((10,10), (10,0), (5,5)) = -50 | -100 | same sign: prev = -50 |
| 4 | 3 | (5,5) | cross((10,0), (5,5), (0,0)) = 50 | -50 | opposite sign: return False |
The dent is found at i = 3, whose third point points[(3 + 2) % 5] is points[0]: without the wrap-around the loop would stop at i = 2 and answer true.
| 1 | The sign of `cross(o, a, b)` tells which way `o -> a -> b` turns: positive left, negative right, 0 straight. A convex polygon turns the same way at every corner. |
| 2 | Keep `prev`, the last non-zero turn; the polygon is convex exactly when no non-zero `turn` has the opposite sign. |
| 3 | For `i` in `range(n)`: `turn = cross(points[i], points[(i + 1) % n], points[(i + 2) % n])`; skip a 0; return `False` if `prev != 0 and (turn > 0) != (prev > 0)`; else `prev = turn`. Return `True` after the loop. |
| 4 | The trap: `if turn == 0: continue` before any comparison, and never store a 0 in `prev`: a straight corner is allowed, and forgetting the direction there lets a dent right after it slip through. |
Target: Convex Polygon (LeetCode 469). Twice the signed area of the triangle `o, a, b`: positive for a left turn, negative for a right turn, 0 for three points on one line.
Boundary pointers contract inward after each directional sweep; modular arithmetic bounds state cyclically.
while top <= bottom and left <= right: sweep right, down, left, up, contracting respective pointer.
Conceptual Narrative
🧭 Conceptual Foundation & Pattern Intuition
Convexity sounds like a question about angles, but it only needs directions: a polygon is convex exactly when walking along its edge you always turn the same way. The Cross Product measures a turn with one integer and no angle: cross(o, a, b) is positive when the path o -> a -> b turns left, negative when it turns right, and 0 when the three points lie on one line. So is_convex walks the corners once, computes turn at each one, and keeps prev, the last non-zero turn: the first turn whose sign differs from prev is a dent.
🚗 The Analogy: Driving Around a Block
Picture driving once around a city block that has no dents: at every corner you turn the same way, say always right. If you ever have to turn left, the block must bend inward there. Driving straight through a junction is no turn at all, so it tells you nothing: you keep remembering that your turns so far were right turns. The cross product is the steering wheel read as a number: positive for a left turn, negative for a right turn, zero when you go straight on.
🪄 The Mathematical Harmony / Magic Trick
turn = cross(points[i], points[(i + 1) % n], points[(i + 2) % n])if turn == 0: continueif prev != 0 and (turn > 0) != (prev > 0): return Falseprev = turn cross(o, a, b) is (a[0] - o[0]) * (b[1] - o[1]) - (a[1] - o[1]) * (b[0] - o[0]), twice the signed area of the triangle o, a, b. Its sign changes exactly when b moves from one side of the line through o and a to the other, so it measures the turn at a with integer multiplication and subtraction only: no division by zero on a vertical edge, no rounding. The % n indices make the last two turns, at points[n - 1] and points[0], part of the same loop. A turn of 0 is skipped before prev is touched, so a straight corner can neither be mistaken for a dent nor erase the direction the edge was turning.
💡 Summary
Compute turn = cross(...) at every corner with % n wrap-around, skip turns of 0, and return False as soon as a turn's sign differs from prev. One pass: time, extra space.
Straight corners: write
if turn == 0: continuebefore comparing. A straight corner is allowed, and storing its 0 inprevforgets the direction: in[[6,6],[4,12],[0,12],[0,0],[12,0],[12,12],[8,12],[7,9]]the dent at[6,6], checked right after the straight corner[7,9], would pass.No wrap-around: use
points[(i + 1) % n]andpoints[(i + 2) % n]. The last two turns sit atpoints[n - 1]andpoints[0], and in[[0,0],[0,10],[10,10],[10,0],[5,5]]the dent at[5,5]is one of them.Multiplying signs: compare with
(turn > 0) != (prev > 0), notprev * turn < 0. Each cross product reaches about 8 * 10^8, so the product of two overflows a 32-bit integer in Java or C++.Slopes or angles:
dy / dxdivides by zero on a vertical edge andatan2rounds; the cross product stays in exact integers.
4-Phase Thought Process Model
You will see how a senior engineer turns "no dent" into "every turn has the same sign" and says so out loud.
Pattern Recognition Signals
The 10-second spot
"Each point is joined to the next one, and the last point is joined back to the first", "you always turn the same way (only left turns, or only right turns)", "a straight corner is not a turn", and whole-number corners [x, y]: a question about which way the edge turns between points in the plane. That is the signal for the Cross Product: one integer per corner says left, right or straight, with no angle and no division.
Formulating the Predicate & Invariants
Turning intuition into a boolean rule
turn = cross(points[i], points[(i + 1) % n], points[(i + 2) % n]) is the turn at points[(i + 1) % n]: positive for left, negative for right, 0 for straight. prev holds the last non-zero turn, and the polygon is convex exactly when no non-zero turn has the opposite sign to prev.
Silent Failure Traps & Edge Cases
Where confident candidates still lose points
A turn of 0 is a straight corner:
if turn == 0: continuebefore any comparison. Treating it as a change of direction rejects convex polygons with extra points on an edge, and storing it inprevforgets the direction, so the dent at[6,6]in[[6,6],[4,12],[0,12],[0,0],[12,0],[12,12],[8,12],[7,9]], checked right after the straight corner[7,9], would pass.Wrap around with
% n: the turns atpoints[n - 1]andpoints[0]close the loop, and in[[0,0],[0,10],[10,10],[10,0],[5,5]]the dent at[5,5]is one of them.Compare signs with
(turn > 0) != (prev > 0), notprev * turn < 0: the product can reach about6.4 * 1017and overflows a 32-bit integer in Java or C++.No slopes or angles:
dy / dxdivides by zero on a vertical edge andatan2rounds, whilecrossstays in exact integers.
The 60-Second Interview Pitch
Say this out loud before you type a single line
I'd use the Cross Product orientation test. For three points o, a and b, the cross product of a minus o with b minus o is positive when the path turns left, negative when it turns right, and zero when the three points are on one line. A polygon is convex exactly when its edge always turns the same way, so I walk the corners once, compute the turn at each one, and wrap around with modulo n so the two turns that close the loop are checked too. I keep prev, the last non-zero turn, and return false the moment a turn has the opposite sign. The trap is a turn of zero: that's a straight corner, which is allowed, so I skip it instead of calling it a dent or letting it erase prev. Everything stays in integers, with no division and no angles. That's
O(N)time andO(1)extra space.
So: one cross product per corner, % n wrap-around, straight corners skipped, and the first sign change is the dent.
Complexity & Mathematical Proof
O(N)
Count the work in is_convex. The loop for i in range(n) runs once per corner, N times. Each pass calls cross once, which does four subtractions, two multiplications and one more subtraction: O(1) whatever the coordinates. The test turn == 0, the sign comparison with prev and the assignment prev = turn are O(1) too. Nothing else loops, so the total is at most N passes of constant work: O(N). A dent can stop the loop early, but a convex polygon (the worst case) visits every corner.
O(1)
is_convex keeps n, i, turn and prev, and each call to cross keeps three references and returns one integer: O(1). The % n indices read points[0] and points[1] again instead of copying them to the end of a new list, so nothing grows with N.
T(N) = N · (one cross product + two comparisons) = O(N)
Count the work in is_convex. The loop for i in range(n) runs once per corner, N times. Each pass calls cross once, which does four subtractions, two multiplications and one more subtraction: O(1) whatever the coordinates. The test turn == 0, the sign comparison with prev and the assignment prev = turn are O(1) too. Nothing else loops, so the total is at most N passes of constant work: O(N). A dent can stop the loop early, but a convex polygon (the worst case) visits every corner.
Derivation Progression
N
for i in range(n) runs once per corner; the % n indices reach the two turns that close the loop without a second pass.
O(1)
cross does a fixed number of subtractions and two multiplications, whatever the coordinates.
O(1)
turn == 0 and (turn > 0) != (prev > 0) are two comparisons; prev = turn is one assignment.
O(N)
N passes of constant work; a dent can only stop the loop sooner.
Variable Definitions
Number of corners, len(points) (at most 10^4)
Memory Architecture & Bounds
O(1): one call to cross at a time, no recursion
O(1): n, i, turn, prev
O(1): one boolean
Boundary Best / Worst Cases
: the second turn already goes the other way
: a convex polygon, where every corner is checked
Recurrence Tree Topology
Senior SWE Deconstruction & Hardware Caveats
Triggers: "you always turn the same way", "no dent", "a straight corner is not a turn", whole-number corners [x, y] joined in order. A question about the direction of turns between integer points: Cross Product, the sign of one integer per corner.
Up to corners with coordinates in . Each difference is below , so one cross product stays below and fits a 32-bit integer, but the product of two does not. One pass is cross products; testing every corner against every edge would be .
Real coordinates (GPS, CAD, game physics) are floating-point numbers: the cross product of three nearly collinear points can round to the wrong sign, so two tests can disagree about the same corner. Production geometry code uses exact or adaptive-precision arithmetic for this test, or snaps coordinates to an integer grid first, instead of a loose tolerance. A polygon streamed from disk only needs its first two corners (for the wrap-around) and the current three in memory.
Core Algorithmic State Invariants
`cross(o, a, b)` is twice the signed area of the triangle `o, a, b`: positive for a left turn, negative for a right turn, 0 for three points on one line. One integer answers the question with no angle.
`if turn == 0: continue` runs before `prev` is compared or changed, so a straight corner neither flags a dent nor makes the loop forget the direction before the next one.
`% n` checks the two turns that close the loop; `N` cross products and four variables give O(N) time and O(1) extra space.
Convex Polygon (LeetCode 469)
You will see how the sign of one integer per corner tells whether a polygon has a dent.
points lists the corners of a polygon in the order you meet them when you walk along its edge: each point is joined to the next one, and the last point is joined back to the first. The polygon is guaranteed to be simple: every corner touches exactly two edges, and no two edges meet or cross anywhere else.
Return true if the polygon is convex and false if it is not. A convex polygon has no dent: walking around it, you always turn the same way (only left turns, or only right turns). Three corners in a row may lie on one straight line; such a straight corner is not a turn, so it never makes the polygon non-convex.
Worked Examples
points = [[0,0],[0,5],[5,5],[5,0]]truepoints = [[0,0],[0,10],[10,10],[10,0],[5,5]]false⚖️Formal Constraints & Bounds
3 <= points.length <= 104points[i].length == 2-104 <= xi, yi <= 104All the given points are unique.
Why It Works & Core Invariant
One integer, cross(o, a, b), says whether the edge turns left or right at a corner. A polygon is convex exactly when every non-zero turn has the same sign, and a turn of 0 (a straight corner) changes nothing.
Real-World Scenario & Production Applications
A map or CAD tool checking that a drawn outline (a building footprint, a delivery zone, a collision shape in a game) has no dent before handing it to an algorithm that only works on convex shapes, such as a fast point-in-polygon test or a separating-axis collision check.
Subproblems & Recurrence Decomposition3 Phases
Establish 4-wall perimeter bounding (top, bottom, left, right) or binary exponent halving state x^n = (x^2)^(n/2).
top, bottom = 0, R - 1
left, right = 0, C - 1
res = []Step-by-Step Execution Trace Table
Example 2, points = [[0,0],[0,10],[10,10],[10,0],[5,5]] (n = 5):
| Step | i | Corner points[(i + 1) % n] | turn | prev before | Result |
|---|---|---|---|---|---|
| 1 | 0 | (0,10) | cross((0,0), (0,10), (10,10)) = -100 | 0 | first turn: prev = -100 (right) |
| 2 | 1 | (10,10) | cross((0,10), (10,10), (10,0)) = -100 | -100 | same sign: prev = -100 |
| 3 | 2 | (10,0) | cross((10,10), (10,0), (5,5)) = -50 | -100 | same sign: prev = -50 |
| 4 | 3 | (5,5) | cross((10,0), (5,5), (0,0)) = 50 | -50 | opposite sign: return False |
The dent is found at i = 3, whose third point points[(3 + 2) % 5] is points[0]: without the wrap-around the loop would stop at i = 2 and answer true.
| 1 | The sign of `cross(o, a, b)` tells which way `o -> a -> b` turns: positive left, negative right, 0 straight. A convex polygon turns the same way at every corner. |
| 2 | Keep `prev`, the last non-zero turn; the polygon is convex exactly when no non-zero `turn` has the opposite sign. |
| 3 | For `i` in `range(n)`: `turn = cross(points[i], points[(i + 1) % n], points[(i + 2) % n])`; skip a 0; return `False` if `prev != 0 and (turn > 0) != (prev > 0)`; else `prev = turn`. Return `True` after the loop. |
| 4 | The trap: `if turn == 0: continue` before any comparison, and never store a 0 in `prev`: a straight corner is allowed, and forgetting the direction there lets a dent right after it slip through. |
Target: Convex Polygon (LeetCode 469). Twice the signed area of the triangle `o, a, b`: positive for a left turn, negative for a right turn, 0 for three points on one line.
Boundary pointers contract inward after each directional sweep; modular arithmetic bounds state cyclically.
while top <= bottom and left <= right: sweep right, down, left, up, contracting respective pointer.
Conceptual Narrative
🧭 Conceptual Foundation & Pattern Intuition
Convexity sounds like a question about angles, but it only needs directions: a polygon is convex exactly when walking along its edge you always turn the same way. The Cross Product measures a turn with one integer and no angle: cross(o, a, b) is positive when the path o -> a -> b turns left, negative when it turns right, and 0 when the three points lie on one line. So is_convex walks the corners once, computes turn at each one, and keeps prev, the last non-zero turn: the first turn whose sign differs from prev is a dent.
🚗 The Analogy: Driving Around a Block
Picture driving once around a city block that has no dents: at every corner you turn the same way, say always right. If you ever have to turn left, the block must bend inward there. Driving straight through a junction is no turn at all, so it tells you nothing: you keep remembering that your turns so far were right turns. The cross product is the steering wheel read as a number: positive for a left turn, negative for a right turn, zero when you go straight on.
🪄 The Mathematical Harmony / Magic Trick
turn = cross(points[i], points[(i + 1) % n], points[(i + 2) % n])if turn == 0: continueif prev != 0 and (turn > 0) != (prev > 0): return Falseprev = turn cross(o, a, b) is (a[0] - o[0]) * (b[1] - o[1]) - (a[1] - o[1]) * (b[0] - o[0]), twice the signed area of the triangle o, a, b. Its sign changes exactly when b moves from one side of the line through o and a to the other, so it measures the turn at a with integer multiplication and subtraction only: no division by zero on a vertical edge, no rounding. The % n indices make the last two turns, at points[n - 1] and points[0], part of the same loop. A turn of 0 is skipped before prev is touched, so a straight corner can neither be mistaken for a dent nor erase the direction the edge was turning.
💡 Summary
Compute turn = cross(...) at every corner with % n wrap-around, skip turns of 0, and return False as soon as a turn's sign differs from prev. One pass: time, extra space.
Straight corners: write
if turn == 0: continuebefore comparing. A straight corner is allowed, and storing its 0 inprevforgets the direction: in[[6,6],[4,12],[0,12],[0,0],[12,0],[12,12],[8,12],[7,9]]the dent at[6,6], checked right after the straight corner[7,9], would pass.No wrap-around: use
points[(i + 1) % n]andpoints[(i + 2) % n]. The last two turns sit atpoints[n - 1]andpoints[0], and in[[0,0],[0,10],[10,10],[10,0],[5,5]]the dent at[5,5]is one of them.Multiplying signs: compare with
(turn > 0) != (prev > 0), notprev * turn < 0. Each cross product reaches about 8 * 10^8, so the product of two overflows a 32-bit integer in Java or C++.Slopes or angles:
dy / dxdivides by zero on a vertical edge andatan2rounds; the cross product stays in exact integers.
4-Phase Thought Process Model
You will see how a senior engineer turns "no dent" into "every turn has the same sign" and says so out loud.
Pattern Recognition Signals
The 10-second spot
"Each point is joined to the next one, and the last point is joined back to the first", "you always turn the same way (only left turns, or only right turns)", "a straight corner is not a turn", and whole-number corners [x, y]: a question about which way the edge turns between points in the plane. That is the signal for the Cross Product: one integer per corner says left, right or straight, with no angle and no division.
Formulating the Predicate & Invariants
Turning intuition into a boolean rule
turn = cross(points[i], points[(i + 1) % n], points[(i + 2) % n]) is the turn at points[(i + 1) % n]: positive for left, negative for right, 0 for straight. prev holds the last non-zero turn, and the polygon is convex exactly when no non-zero turn has the opposite sign to prev.
Silent Failure Traps & Edge Cases
Where confident candidates still lose points
A turn of 0 is a straight corner:
if turn == 0: continuebefore any comparison. Treating it as a change of direction rejects convex polygons with extra points on an edge, and storing it inprevforgets the direction, so the dent at[6,6]in[[6,6],[4,12],[0,12],[0,0],[12,0],[12,12],[8,12],[7,9]], checked right after the straight corner[7,9], would pass.Wrap around with
% n: the turns atpoints[n - 1]andpoints[0]close the loop, and in[[0,0],[0,10],[10,10],[10,0],[5,5]]the dent at[5,5]is one of them.Compare signs with
(turn > 0) != (prev > 0), notprev * turn < 0: the product can reach about6.4 * 1017and overflows a 32-bit integer in Java or C++.No slopes or angles:
dy / dxdivides by zero on a vertical edge andatan2rounds, whilecrossstays in exact integers.
The 60-Second Interview Pitch
Say this out loud before you type a single line
I'd use the Cross Product orientation test. For three points o, a and b, the cross product of a minus o with b minus o is positive when the path turns left, negative when it turns right, and zero when the three points are on one line. A polygon is convex exactly when its edge always turns the same way, so I walk the corners once, compute the turn at each one, and wrap around with modulo n so the two turns that close the loop are checked too. I keep prev, the last non-zero turn, and return false the moment a turn has the opposite sign. The trap is a turn of zero: that's a straight corner, which is allowed, so I skip it instead of calling it a dent or letting it erase prev. Everything stays in integers, with no division and no angles. That's
O(N)time andO(1)extra space.
So: one cross product per corner, % n wrap-around, straight corners skipped, and the first sign change is the dent.
Complexity & Mathematical Proof
O(N)
Count the work in is_convex. The loop for i in range(n) runs once per corner, N times. Each pass calls cross once, which does four subtractions, two multiplications and one more subtraction: O(1) whatever the coordinates. The test turn == 0, the sign comparison with prev and the assignment prev = turn are O(1) too. Nothing else loops, so the total is at most N passes of constant work: O(N). A dent can stop the loop early, but a convex polygon (the worst case) visits every corner.
O(1)
is_convex keeps n, i, turn and prev, and each call to cross keeps three references and returns one integer: O(1). The % n indices read points[0] and points[1] again instead of copying them to the end of a new list, so nothing grows with N.
T(N) = N · (one cross product + two comparisons) = O(N)
Count the work in is_convex. The loop for i in range(n) runs once per corner, N times. Each pass calls cross once, which does four subtractions, two multiplications and one more subtraction: O(1) whatever the coordinates. The test turn == 0, the sign comparison with prev and the assignment prev = turn are O(1) too. Nothing else loops, so the total is at most N passes of constant work: O(N). A dent can stop the loop early, but a convex polygon (the worst case) visits every corner.
Derivation Progression
N
for i in range(n) runs once per corner; the % n indices reach the two turns that close the loop without a second pass.
O(1)
cross does a fixed number of subtractions and two multiplications, whatever the coordinates.
O(1)
turn == 0 and (turn > 0) != (prev > 0) are two comparisons; prev = turn is one assignment.
O(N)
N passes of constant work; a dent can only stop the loop sooner.
Variable Definitions
Number of corners, len(points) (at most 10^4)
Memory Architecture & Bounds
O(1): one call to cross at a time, no recursion
O(1): n, i, turn, prev
O(1): one boolean
Boundary Best / Worst Cases
: the second turn already goes the other way
: a convex polygon, where every corner is checked
Recurrence Tree Topology
Senior SWE Deconstruction & Hardware Caveats
Triggers: "you always turn the same way", "no dent", "a straight corner is not a turn", whole-number corners [x, y] joined in order. A question about the direction of turns between integer points: Cross Product, the sign of one integer per corner.
Up to corners with coordinates in . Each difference is below , so one cross product stays below and fits a 32-bit integer, but the product of two does not. One pass is cross products; testing every corner against every edge would be .
Real coordinates (GPS, CAD, game physics) are floating-point numbers: the cross product of three nearly collinear points can round to the wrong sign, so two tests can disagree about the same corner. Production geometry code uses exact or adaptive-precision arithmetic for this test, or snaps coordinates to an integer grid first, instead of a loose tolerance. A polygon streamed from disk only needs its first two corners (for the wrap-around) and the current three in memory.
Core Algorithmic State Invariants
`cross(o, a, b)` is twice the signed area of the triangle `o, a, b`: positive for a left turn, negative for a right turn, 0 for three points on one line. One integer answers the question with no angle.
`if turn == 0: continue` runs before `prev` is compared or changed, so a straight corner neither flags a dent nor makes the loop forget the direction before the next one.
`% n` checks the two turns that close the loop; `N` cross products and four variables give O(N) time and O(1) extra space.
| Canonical Invariant | Concrete Code | Engineering Rationale |
|---|---|---|
| Orientation test: the sign of one integer is the turn | return (a[0] - o[0]) * (b[1] - o[1]) - (a[1] - o[1]) * (b[0] - o[0]) | Twice the signed area of the triangle `o, a, b`: positive for a left turn, negative for a right turn, 0 for three points on one line. |
| Remember the last real turn | prev = 0 | 0 means no turn has been seen yet; after that it always holds the last non-zero turn. |
| Visit every corner, wrapping around | for i in range(n):
turn = cross(points[i], points[(i + 1) % n], points[(i + 2) % n]) | `% n` makes the turns at `points[n - 1]` and `points[0]`, which close the loop, part of the same pass. |
| A straight corner is not a turn (the trap) | if turn == 0:
continue | It is skipped before `prev` is touched: it never counts as a dent and never erases the direction. |
| A turn the other way is a dent | if prev != 0 and (turn > 0) != (prev > 0):
return False | Comparing signs instead of multiplying keeps the test exact and free of overflow. |
| Carry the direction forward | prev = turn
return True | Only non-zero turns reach this line; if the loop ends, every turn went the same way. |