Check If It Is a Straight Line
All points lie on one line iff every point shares the cross-product direction with the first edge.
3 min read
geometry math cross-product
Problem#
Return true iff all given 2D points lie on a single straight line.
Examples#
[[1,2],[2,3],[3,4],[4,5]]→true.[[1,1],[2,2],[3,4]]→false.
Constraints#
2 <= coordinates.length <= 1000.
Approach#
Fix the first two points as the reference edge. For each later point, check the cross product of (p1 → p2) and (p1 → pk) is zero.
Solution#
class Solution {public: bool checkStraightLine(vector<vector<int>>& c) { long long dx = c[1][0] - c[0][0], dy = c[1][1] - c[0][1]; for (int i = 2; i < (int)c.size(); ++i) { long long ex = c[i][0] - c[0][0], ey = c[i][1] - c[0][1]; if (dx * ey - dy * ex != 0) return false; } return true; }};func checkStraightLine(coordinates [][]int) bool { dx := int64(coordinates[1][0] - coordinates[0][0]) dy := int64(coordinates[1][1] - coordinates[0][1]) for i := 2; i < len(coordinates); i++ { ex := int64(coordinates[i][0] - coordinates[0][0]) ey := int64(coordinates[i][1] - coordinates[0][1]) if dx*ey-dy*ex != 0 { return false } } return true}from typing import List
class Solution: def checkStraightLine(self, coordinates: List[List[int]]) -> bool: dx = coordinates[1][0] - coordinates[0][0] dy = coordinates[1][1] - coordinates[0][1] for i in range(2, len(coordinates)): ex = coordinates[i][0] - coordinates[0][0] ey = coordinates[i][1] - coordinates[0][1] if dx * ey - dy * ex != 0: return False return Truevar checkStraightLine = function(coordinates) { const dx = coordinates[1][0] - coordinates[0][0]; const dy = coordinates[1][1] - coordinates[0][1]; for (let i = 2; i < coordinates.length; i++) { const ex = coordinates[i][0] - coordinates[0][0]; const ey = coordinates[i][1] - coordinates[0][1]; if (dx * ey - dy * ex !== 0) return false; } return true;};class Solution { public boolean checkStraightLine(int[][] coordinates) { long dx = coordinates[1][0] - coordinates[0][0]; long dy = coordinates[1][1] - coordinates[0][1]; for (int i = 2; i < coordinates.length; i++) { long ex = coordinates[i][0] - coordinates[0][0]; long ey = coordinates[i][1] - coordinates[0][1]; if (dx * ey - dy * ex != 0) return false; } return true; }}function checkStraightLine(coordinates: number[][]): boolean { const dx = coordinates[1][0] - coordinates[0][0]; const dy = coordinates[1][1] - coordinates[0][1]; for (let i = 2; i < coordinates.length; i++) { const ex = coordinates[i][0] - coordinates[0][0]; const ey = coordinates[i][1] - coordinates[0][1]; if (dx * ey - dy * ex !== 0) return false; } return true;}Editorial#
Cross product is the right tool — it sidesteps division-by-zero for vertical lines and gives an exact integer answer for integer inputs.
Complexity#
- Time:
O(n). - Space:
O(1).
Concept revision#
Related#