Skip to content

1232. Check If It Is a Straight Line

SourceWeekly Contest 159 Q1DifficultyEasyRating1247

Description

You are given an integer 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.

 

 

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^4 <= coordinates[i][0], coordinates[i][1] <= 10^4
  • coordinates contains no duplicate point.

Solutions

Solution 1: Mathematics

Thinking

Points are collinear iff every vector from the first point is parallel to the first edge. Comparing slopes hits vertical lines and floating error. The cross product \((x-x_1)(y_2-y_1)=(y-y_1)(x_2-x_1)\) avoids division.

We fix the first two points and test the identity on the rest. \(n \le 1000\) allows one linear pass. Points are distinct, so there is no zero vector.

The time complexity is \(O(n)\), where \(n\) is the length of the coordinates array. The space complexity is \(O(1)\).

1
2
3
4
5
6
7
8
class Solution:
    def checkStraightLine(self, coordinates: List[List[int]]) -> bool:
        x1, y1 = coordinates[0]
        x2, y2 = coordinates[1]
        for x, y in coordinates[2:]:
            if (x - x1) * (y2 - y1) != (y - y1) * (x2 - x1):
                return False
        return True

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
class Solution {
    public boolean checkStraightLine(int[][] coordinates) {
        int x1 = coordinates[0][0], y1 = coordinates[0][1];
        int x2 = coordinates[1][0], y2 = coordinates[1][1];
        for (int i = 2; i < coordinates.length; ++i) {
            int x = coordinates[i][0], y = coordinates[i][1];
            if ((x - x1) * (y2 - y1) != (y - y1) * (x2 - x1)) {
                return false;
            }
        }
        return true;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
class Solution {
public:
    bool checkStraightLine(vector<vector<int>>& coordinates) {
        int x1 = coordinates[0][0], y1 = coordinates[0][1];
        int x2 = coordinates[1][0], y2 = coordinates[1][1];
        for (int i = 2; i < coordinates.size(); ++i) {
            int x = coordinates[i][0], y = coordinates[i][1];
            if ((x - x1) * (y2 - y1) != (y - y1) * (x2 - x1)) {
                return false;
            }
        }
        return true;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
func checkStraightLine(coordinates [][]int) bool {
    x1, y1 := coordinates[0][0], coordinates[0][1]
    x2, y2 := coordinates[1][0], coordinates[1][1]
    for i := 2; i < len(coordinates); i++ {
        x, y := coordinates[i][0], coordinates[i][1]
        if (x-x1)*(y2-y1) != (y-y1)*(x2-x1) {
            return false
        }
    }
    return true
}

Comments