Check If It Is a Straight Line

Difficulty: Easy | Acceptance: 40.10% | Paid: No Topics: Array, Math, Geometry

You are given an array coordinates, coordinates[i] = [x, y], where [x, y] represents the coordinate of a point. Check if these points make a straight line in the XY plane.

• Examples
• Constraints
• Cross Product Method
• Slope Ratio Comparison
• Area of Triangle Method

Examples

Example 1

Input:

coordinates = [[1,2],[2,3],[3,4],[4,5],[5,6],[6,7]]

Output:

true

Example 2

Input:

coordinates = [[1,1],[2,2],[3,4],[4,5],[5,6],[7,7]]

Output:

false

Constraints

2 <= coordinates.length <= 1000
coordinates[i].length == 2
-10⁴ <= coordinates[i][0], coordinates[i][1] <= 10⁴
coordinates contains no duplicate point.

Cross Product Method

Intuition For points to be collinear, the slope between any point and a reference point must be equal. Instead of using division (which causes precision issues), we use cross product to compare slopes.

Steps

• Use the first two points to establish the reference direction
• For each remaining point, check if the cross product with the reference direction is zero
• If all cross products are zero, all points lie on the same line

from typing import List

class Solution:
    def checkStraightLine(self, coordinates: List[List[int]]) -> bool:
        n = len(coordinates)
        if n <= 2:
            return True
        
        x0, y0 = coordinates[0]
        x1, y1 = coordinates[1]
        
        for i in range(2, n):
            xi, yi = coordinates[i]
            # Cross product: (y1 - y0) * (xi - x0) == (yi - y0) * (x1 - x0)
            if (y1 - y0) * (xi - x0) != (yi - y0) * (x1 - x0):
                return False
        
        return True

Complexity

• Time: O(n) where n is the number of coordinates
• Space: O(1) only using constant extra space
• Notes: Avoids floating-point precision issues by using integer cross product comparison

Slope Ratio Comparison

Intuition Compare the slope ratio (Δy/Δx) between consecutive points by cross-multiplying to avoid division. This is essentially the same as the cross product method but compares consecutive point pairs.

Steps

• Calculate the delta X and delta Y between the first two points
• For each consecutive pair of points, verify their delta ratio matches the reference
• Use cross-multiplication to avoid division and precision issues

from typing import List

class Solution:
    def checkStraightLine(self, coordinates: List[List[int]]) -> bool:
        n = len(coordinates)
        if n <= 2:
            return True
        
        # Reference delta from first two points
        dx0 = coordinates[1][0] - coordinates[0][0]
        dy0 = coordinates[1][1] - coordinates[0][1]
        
        for i in range(2, n):
            dx = coordinates[i][0] - coordinates[i-1][0]
            dy = coordinates[i][1] - coordinates[i-1][1]
            # Compare slopes using cross product: dy0 * dx == dy * dx0
            if dy0 * dx != dy * dx0:
                return False
        
        return True

Complexity

• Time: O(n) where n is the number of coordinates
• Space: O(1) only using constant extra space
• Notes: Compares consecutive segments instead of all points to a reference

Area of Triangle Method

Intuition Three points are collinear if and only if the area of the triangle formed by them is zero. We can use the determinant formula to check this condition for every triplet of consecutive points.

Steps

• For each triplet of consecutive points, calculate the determinant
• The determinant |x1 y1 1; x2 y2 1; x3 y3 1| equals twice the signed area
• If all determinants are zero, all points are collinear

from typing import List

class Solution:
    def checkStraightLine(self, coordinates: List[List[int]]) -> bool:
        n = len(coordinates)
        if n <= 2:
            return True
        
        x0, y0 = coordinates[0]
        x1, y1 = coordinates[1]
        
        for i in range(2, n):
            x2, y2 = coordinates[i]
            # Determinant = x0(y1 - y2) + x1(y2 - y0) + x2(y0 - y1)
            # If determinant is 0, points are collinear
            if x0 * (y1 - y2) + x1 * (y2 - y0) + x2 * (y0 - y1) != 0:
                return False
        
        return True

Complexity

• Time: O(n) where n is the number of coordinates
• Space: O(1) only using constant extra space
• Notes: Uses the geometric property that collinear points form a triangle with zero area