Check If It Is a Straight Line

Problem Statement

You have been provided with an array coordinates, where each element coordinates[i] contains a pair [x, y]. Each pair represents the x and y coordinates of a point on a 2D plane. The primary challenge is to determine if all these points lie on a straight line. The problem demands analyzing the alignment of the points using their X-Y plane positions and deciding whether they linearly align or not. This requires consideration of geometric properties and possibly calculating the slope or using some other geometric or algebraic method to verify the straight-line alignment of the given points.

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

Approach and Intuition

To understand if the points represented by the coordinates form a straight line, we can use a straightforward approach:

1. Calculating the Slope:

   • The slope between any two given points (x1, y1) and (x2, y2) is (y2 - y1) / (x2 - x1). This simple mathematical property can be used to determine linearity. A group of points lie on the same straight line if the slope between consecutive points remains constant.

2. Handling Vertical Lines:

   • Special consideration is needed for vertical lines where x1 = x2, as the slope formula would lead to division by zero. For such cases, we can check simply if all x-coordinates are the same.

3. Iterative Comparison:

   • Starting from the initial two points, calculate the slope and then, iterate through the array, comparing the slope of the line segments formed by consecutive points. If at any point the slope differs from the initial one, we return false, indicating the points do not form a straight line.

4. Mathematical Consistency and Precision:

   • To avoid precision errors from floating division for slope calculation, use a cross multiplication method: (y2 - y1) * (x3 - x2) = (y3 - y2) * (x2 - x1). This formula helps maintain consistency without dividing numbers.

The two provided examples perfectly illustrate the above method:

• Example 1:

  • Here, each consecutive point set increases by 1 on both x and y axis consistently ([1,2] to [2,3], and so on), maintaining a constant slope. The result is true.

• Example 2:

  • The change from [3,4] to [4,5] introduces a different slope compared to the rest, thus, the output is false.

This analysis shows that checking if a list of points lie on a straight line can be efficiently accomplished using slope comparisons without directly computing the angles or distances, thus making the solution more robust against common geometric pitfalls such as floating-point arithmetic issues.

Solutions

class Solution {
public:
    // Calculate vertical difference
    int verticalDifference(vector<int>& point1, vector<int>& point2) {
        return point1[1] - point2[1];
    }
    
    // Calculate horizontal difference
    int horizontalDifference(vector<int>& point1, vector<int>& point2) {
        return point1[0] - point2[0];
    }
    
    bool isLineStraight(vector<vector<int>>& points) {
        int diffY = verticalDifference(points[1], points[0]);
        int diffX = horizontalDifference(points[1], points[0]);
        
        for (int i = 2; i < points.size(); i++) {
            // Verify if current point maintains linearity
            if (diffY * horizontalDifference(points[i], points[0])
                != diffX * verticalDifference(points[i], points[0])) {
                return false;
            }
        }
        return true;
    }
};

class Solution {
    int calculateYDelta(int[] point1, int[] point2) {
        return point1[1] - point2[1];
    }
    
    int calculateXDelta(int[] point1, int[] point2) {
        return point1[0] - point2[0];
    }
    
    public boolean arePointsCollinear(int[][] points) {
        int yDifference = calculateYDelta(points[1], points[0]);
        int xDifference = calculateXDelta(points[1], points[0]);
        
        for (int i = 2; i < points.length; i++) {
            if (yDifference * calculateXDelta(points[i], points[0])
                != xDifference * calculateYDelta(points[i], points[0])) {
                return false;
            }
        }
        return true;
    }
}