Check If It Is a Straight Line
Easy · Geometry · Array · Math · Geometry
Problem
You are given a list of points on a plane, coordinates, where each point is [x, y]. Return True if all of the points lie on one straight line, otherwise False.
The points can come in any order along the line, and no point appears twice. With only two points the answer is always True, because any two distinct points define a line.
Examples
Input: coordinates = [[1,2],[2,3],[3,4],[4,5],[5,6],[6,7]] Output: True
Every point is one step right and one step up from the one before, so all six are on the line y = x + 1.
Input: coordinates = [[1,1],[2,2],[3,4],[4,5],[5,6],[7,7]] Output: False
The first two points are on y = x, but (3, 4) is not: the cross product 1 * (4 - 1) - 1 * (3 - 1) is 1, not 0.
Input: coordinates = [[3,-2],[3,5],[3,0],[3,9]] Output: True
All four points have x = 3. The slope would divide by zero, but the cross product 0 * (y - y0) - 7 * (3 - 3) is 0 for each of them.
Constraints
- 2 <= len(coordinates) <= 1000
- coordinates[i] == [x, y]
- -10^4 <= x, y <= 10^4
- no two points are the same
Approaches
- Baseline: compare slopes as exact fractions — time O(n log C), C the coordinate range, space O(1)
Follow-up
What if points can repeat? Then the first two points may be the same, and they no longer fix a line. Use the first point that differs from coordinates[0] as the second anchor, and answer True if there is none. The cross product test itself does not change.
Related problems
Start free on Cariara · Coding problems · System design studio
