Problem Description

You are given an array coordinates, where each element is a pair of integers representing the x and y coordinates of a point on a 2D plane. Your task is to determine if all the points lie on a single straight line.

Constraints:

• There are at least two points in coordinates.
• Each coordinate is a list of two integers: [x, y].
• You must check if all points are collinear (i.e., form a straight line).
• No point is reused or duplicated; each is unique.

Thought Process

At first glance, the simplest way to solve this problem is to check if the slope between every pair of points is the same. If every point has the same slope with respect to the first point, then all points must lie on a straight line.

However, directly calculating slopes using division can cause issues with division by zero (vertical lines) and floating-point precision errors. To avoid this, we can use cross multiplication to compare slopes without actually dividing.

The process involves:

• Calculating the direction vector between the first two points.
• For each subsequent point, checking if the vector from the first point to that point is proportional (i.e., has the same direction) as the initial direction vector.
• This can be checked using the concept of the area of a triangle (which should be zero for collinear points), or by ensuring the cross product is zero.

Solution Approach

We will use the cross product to check for collinearity. Here's a step-by-step breakdown:

1. Calculate the direction vector:
   Let the first two points be (x0, y0) and (x1, y1). The direction vector is dx = x1 - x0, dy = y1 - y0.
2. Check each subsequent point:
   For each point (xi, yi) (starting from the third point), compute the vector from the first point: (xi - x0, yi - y0).
3. Use the cross product:
   For all points to be collinear, the cross product of the direction vector and each new vector should be zero:
   (xi - x0) * dy - (yi - y0) * dx == 0
4. Return result:
   If all such checks pass, return True. Otherwise, return False.

This method avoids floating-point division and works for all line orientations, including vertical and horizontal lines.

Example Walkthrough

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

1. The first two points are (1,2) and (2,3).
   Direction vector: dx = 2-1 = 1, dy = 3-2 = 1.
2. For the third point (3,4):
   • Vector from first point: (3-1, 4-2) = (2,2)
   • Cross product: 2*1 - 2*1 = 0
3. Repeat for each subsequent point:
   • (4,5): (4-1, 5-2) = (3,3); 3*1 - 3*1 = 0
   • (5,6): (5-1, 6-2) = (4,4); 4*1 - 4*1 = 0
   • (6,7): (6-1, 7-2) = (5,5); 5*1 - 5*1 = 0
4. Since all cross products are zero, all points are collinear. Return True.

If any cross product was non-zero, we would return False.

Time and Space Complexity

Brute-force approach:
If we checked the slope between every pair of points, the time complexity would be O(N^2) where N is the number of points.

Optimized approach (cross product):
We only need to check each point once after the first two, so the time complexity is O(N).
The space complexity is O(1) since we use only a constant amount of extra space.

Summary

The key insight is to compare the direction of each point relative to the first point using the cross product, which elegantly avoids issues with division and precision. By leveraging this geometric property, we achieve a linear time solution that is both robust and efficient. This approach works for all lines, including vertical and horizontal, making it a clean and reliable strategy for checking if points are collinear.

Code Implementation

class Solution:
    def checkStraightLine(self, coordinates):
        x0, y0 = coordinates[0]
        x1, y1 = coordinates[1]
        dx = x1 - x0
        dy = y1 - y0
        for x, y in coordinates[2:]:
            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 < 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 {
    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;
    }
}
      

var checkStraightLine = function(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 ((x - x0) * dy !== (y - y0) * dx)
            return false;
    }
    return true;
};