Check If It Is a Straight Line

easy math geometry

Problem

Given an array of 2D points, return true if they all lie on a single straight line. To avoid division and floating point issues, compare cross products instead of slopes.

Inputcoordinates = [[1,2],[2,3],[3,4],[4,5]]

Outputtrue

For each point i ≥ 2: (x1−x0)*(yi−y0) == (y1−y0)*(xi−x0).

points (e.g. 1,2;2,3;3,4;4,5)

def check_straight_line(coordinates):
    (x0, y0), (x1, y1) = coordinates[0], coordinates[1]
    dx, dy = x1 - x0, y1 - y0
    for x, y in coordinates[2:]:
        if dx * (y - y0) != dy * (x - x0):
            return False
    return True

function checkStraightLine(coordinates) {
  const [x0, y0] = coordinates[0];
  const [x1, y1] = coordinates[1];
  const dx = x1 - x0, dy = y1 - y0;
  for (let i = 2; i < coordinates.length; i++) {
    const [x, y] = coordinates[i];
    if (dx * (y - y0) !== dy * (x - x0)) return false;
  }
  return true;
}

class Solution {
    public boolean checkStraightLine(int[][] c) {
        int x0 = c[0][0], y0 = c[0][1];
        int dx = c[1][0] - x0, dy = c[1][1] - y0;
        for (int i = 2; i < c.length; i++) {
            int x = c[i][0], y = c[i][1];
            if (dx * (y - y0) != dy * (x - x0)) return false;
        }
        return true;
    }
}

bool checkStraightLine(vector<vector<int>>& c) {
    int x0 = c[0][0], y0 = c[0][1];
    int dx = c[1][0] - x0, dy = c[1][1] - y0;
    for (int i = 2; i < (int)c.size(); i++) {
        int x = c[i][0], y = c[i][1];
        if (dx * (y - y0) != dy * (x - x0)) return false;
    }
    return true;
}

Explanation

To test if every point sits on one line, we compare directions using a cross product instead of slopes. That dodges division and the floating-point errors it brings.

We anchor on the first point (x0, y0) and form a reference direction (dx, dy) toward the second point. A third point (x, y) is on the same line only if the vector from the anchor to it points the same way as the reference.

Two vectors are parallel when their cross product is zero, which rearranges into the clean integer test dx * (y - y0) == dy * (x - x0). If any point breaks this equality, we return false right away.

Using multiplication instead of dy/dx keeps everything in whole numbers, so vertical lines (where dx = 0) and rounding are never a problem.

Example: [[1,2],[2,3],[3,4],[4,5]] gives dx=1, dy=1. For point (3,4): 1*(4-2) = 2 and 1*(3-1) = 2 — equal. Every point passes, so the answer is true.

Time: O(n) Space: O(1)