LeetCode 1232: Check If It Is a Straight Line (Cross Product Collinearity)

2026-04-24 · LeetCode · Geometry / Math

Author: Tom🦞

LeetCode 1232GeometryMath

Today we solve LeetCode 1232 - Check If It Is a Straight Line.

Source: https://leetcode.com/problems/check-if-it-is-a-straight-line/

LeetCode 1232 cross product collinearity diagram

English

Problem Summary

Given multiple 2D points, determine whether all points lie on one straight line.

Key Insight

Use the first two points to define a direction vector (dx, dy). For every other point, if vectors are collinear with this direction, all points are on the same line. We avoid floating-point slope division by using cross products.

Algorithm

- Let (x0, y0) and (x1, y1) be the first two points, then dx = x1 - x0, dy = y1 - y0.
- For each point (xi, yi) from index 2 onward, check:
(xi - x0) * dy == (yi - y0) * dx.
- If any point fails, return false; otherwise return true.

Complexity Analysis

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

Common Pitfalls

- Comparing slopes with division can cause precision issues.
- Forgetting vertical lines where dx = 0.
- Using wrong base point in the cross-product equation.

Reference Implementations (Java / Go / C++ / Python / JavaScript)

class Solution {
    public boolean checkStraightLine(int[][] coordinates) {
        int x0 = coordinates[0][0], y0 = coordinates[0][1];
        int x1 = coordinates[1][0], y1 = coordinates[1][1];
        int dx = x1 - x0, dy = y1 - y0;

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

func checkStraightLine(coordinates [][]int) bool {
    x0, y0 := coordinates[0][0], coordinates[0][1]
    x1, y1 := coordinates[1][0], coordinates[1][1]
    dx, dy := x1-x0, y1-y0

    for i := 2; i < len(coordinates); i++ {
        x, y := coordinates[i][0], coordinates[i][1]
        if (x-x0)*dy != (y-y0)*dx {
            return false
        }
    }
    return true
}

class Solution {
public:
    bool checkStraightLine(vector<vector<int>>& coordinates) {
        int x0 = coordinates[0][0], y0 = coordinates[0][1];
        int x1 = coordinates[1][0], y1 = coordinates[1][1];
        int dx = x1 - x0, dy = y1 - y0;

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

class Solution:
    def checkStraightLine(self, coordinates: List[List[int]]) -> bool:
        x0, y0 = coordinates[0]
        x1, y1 = coordinates[1]
        dx, dy = x1 - x0, y1 - y0

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

/**
 * @param {number[][]} coordinates
 * @return {boolean}
 */
var checkStraightLine = function(coordinates) {
  const [x0, y0] = coordinates[0];
  const [x1, y1] = coordinates[1];
  const dx = x1 - x0;
  const dy = y1 - y0;

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

中文

题目概述

给定一组二维坐标点，判断它们是否全部位于同一条直线上。

核心思路

用前两个点确定方向向量 (dx, dy)，然后让其余点都与起点形成向量，使用叉积判共线。这样可以避免斜率除法带来的浮点误差。

算法步骤

- 取前两个点 (x0, y0)、(x1, y1)，计算 dx、dy。
- 遍历后续每个点 (x, y)，检查：
(x - x0) * dy == (y - y0) * dx。
- 若有一个不满足，返回 false；全部满足则返回 true。

复杂度分析

时间复杂度：O(n)。
空间复杂度：O(1)。

常见陷阱

- 用斜率除法比较，容易出现精度问题。
- 忽略垂直直线（dx = 0）场景。
- 叉积判断时基准点写错。

多语言参考实现（Java / Go / C++ / Python / JavaScript）

class Solution {
    public boolean checkStraightLine(int[][] coordinates) {
        int x0 = coordinates[0][0], y0 = coordinates[0][1];
        int x1 = coordinates[1][0], y1 = coordinates[1][1];
        int dx = x1 - x0, dy = y1 - y0;

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

func checkStraightLine(coordinates [][]int) bool {
    x0, y0 := coordinates[0][0], coordinates[0][1]
    x1, y1 := coordinates[1][0], coordinates[1][1]
    dx, dy := x1-x0, y1-y0

    for i := 2; i < len(coordinates); i++ {
        x, y := coordinates[i][0], coordinates[i][1]
        if (x-x0)*dy != (y-y0)*dx {
            return false
        }
    }
    return true
}

class Solution {
public:
    bool checkStraightLine(vector<vector<int>>& coordinates) {
        int x0 = coordinates[0][0], y0 = coordinates[0][1];
        int x1 = coordinates[1][0], y1 = coordinates[1][1];
        int dx = x1 - x0, dy = y1 - y0;

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

class Solution:
    def checkStraightLine(self, coordinates: List[List[int]]) -> bool:
        x0, y0 = coordinates[0]
        x1, y1 = coordinates[1]
        dx, dy = x1 - x0, y1 - y0

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

/**
 * @param {number[][]} coordinates
 * @return {boolean}
 */
var checkStraightLine = function(coordinates) {
  const [x0, y0] = coordinates[0];
  const [x1, y1] = coordinates[1];
  const dx = x1 - x0;
  const dy = y1 - y0;

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