# Check If It Is a Straight Line
**Difficulty:** EASY
[External](https://leetcode.com/problems/check-if-it-is-a-straight-line)
Canonical: https://scaleengineer.com/dsa/problems/check-if-it-is-a-straight-line
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math), [Geometry](https://scaleengineer.com/dsa/patterns/geometry)
**Data structures:** Array
**Companies:** [Palantir Technologies](https://scaleengineer.com/companies/palantir-technologies), [Datadog](https://scaleengineer.com/companies/datadog)
---
## Problem
You are given an 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:**

![](https://assets.glich.co/dsa/check-if-it-is-a-straight-line/image0.jpg)

**Input:** coordinates = [[1,2],[2,3],[3,4],[4,5],[5,6],[6,7]]
**Output:** true

**Example 2:**

**![](https://assets.glich.co/dsa/check-if-it-is-a-straight-line/image1.jpg)**

**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.

# Approaches
## Slope Calculation with Floating-Point Division
This approach works by calculating the slope of the line formed by the first two points. It then iterates through the rest of the points, checking if the slope formed by each point and the first point is identical. This method requires special handling for vertical lines and is susceptible to floating-point precision errors.
**Time:** O(N), where N is the number of points in the `coordinates` array. We iterate through the array once. · **Space:** O(1), as we only use a constant number of variables to store coordinates and the slope.
**Pros:** Conceptually straightforward for those familiar with the slope formula.
**Cons:** Using floating-point numbers for comparison is unreliable due to precision issues.; Requires a separate check to handle vertical lines, making the code more complex.
### Explanation
The fundamental idea is that for a set of points to be on a straight line, the slope between any two pairs of points must be constant. We can simplify this by picking a reference point (e.g., the first point) and checking if the slope between this reference point and all other points is the same.

The algorithm first handles the trivial case where there are 2 or fewer points. Then, it calculates the slope between the first two points. A special case is made for vertical lines where the change in x is zero. For all other points, it calculates the slope with the first point and compares it to the reference slope. Due to the nature of floating-point numbers, direct comparison can be unreliable.

```java
public class Solution {
    public boolean checkStraightLine(int[][] coordinates) {
        if (coordinates.length <= 2) {
            return true;
        }

        int x0 = coordinates[0][0];
        int y0 = coordinates[0][1];
        int x1 = coordinates[1][0];
        int y1 = coordinates[1][1];

        // Handle vertical line case
        if (x1 - x0 == 0) {
            for (int i = 2; i < coordinates.length; i++) {
                if (coordinates[i][0] != x0) {
                    return false;
                }
            }
            return true;
        }

        // Calculate the reference slope
        double slope = (double)(y1 - y0) / (x1 - x0);

        // Check the slope for all other points
        for (int i = 2; i < coordinates.length; i++) {
            int xi = coordinates[i][0];
            int yi = coordinates[i][1];
            // Handle the case where the current pair of points form a vertical line
            if (xi - x0 == 0) {
                return false; // Since the main line is not vertical
            }
            double currentSlope = (double)(yi - y0) / (xi - x0);
            if (currentSlope != slope) {
                return false;
            }
        }

        return true;
    }
}
```
### Algorithm
- 1. If `coordinates.length <= 2`, return `true`.
- 2. Get the first two points `p0(x0, y0)` and `p1(x1, y1)`.
- 3. Check if the line is vertical (`x1 - x0 == 0`).
- 4. If vertical, iterate from the third point and check if all `x` coordinates are equal to `x0`. Return `false` if any differs.
- 5. If not vertical, calculate the slope `m = (y1 - y0) / (x1 - x0)` using floating-point division.
- 6. Iterate from the third point `pi(xi, yi)`.
- 7. Calculate the current slope `current_m = (yi - y0) / (xi - x0)`.
- 8. If `current_m != m`, return `false`.
- 9. If the loop completes, return `true`.

## Cross-Multiplication Method
A more robust and efficient approach is to use the property of collinear points that the area of the triangle formed by any three points is zero. This can be checked using a cross-product formula, which avoids floating-point division and its associated problems. The condition `(y2 - y1) / (x2 - x1) == (y3 - y1) / (x3 - x1)` is transformed into `(y2 - y1) * (x3 - x1) == (y3 - y1) * (x2 - x1)` to avoid division.
**Time:** O(N), where N is the number of points. The algorithm involves a single pass through the input array. · **Space:** O(1). We only use a few integer variables to store the differences and coordinates, regardless of the input size.
**Pros:** Avoids floating-point arithmetic, eliminating precision errors.; Handles all cases (vertical, horizontal, sloped lines) with a single, unified formula.; Generally faster than floating-point calculations.
**Cons:** The mathematical reasoning (cross-product) might be slightly less intuitive than direct slope calculation for some.
### Explanation
To avoid the pitfalls of floating-point arithmetic and division by zero, we can rephrase the slope equality condition. Three points `P0(x0, y0)`, `P1(x1, y1)`, and `Pi(xi, yi)` are collinear if the slope between `(P0, P1)` is equal to the slope between `(P0, Pi)`.

`slope(P0, P1) = (y1 - y0) / (x1 - x0)`
`slope(P0, Pi) = (yi - y0) / (xi - x0)`

Setting them equal: `(y1 - y0) / (x1 - x0) = (yi - y0) / (xi - x0)`

By cross-multiplying to eliminate division, we get:
`(y1 - y0) * (xi - x0) = (yi - y0) * (x1 - x0)`

This equation holds true for vertical, horizontal, and sloped lines and only involves integer arithmetic, making it robust and efficient.

```java
public class Solution {
    public boolean checkStraightLine(int[][] coordinates) {
        if (coordinates.length <= 2) {
            return true;
        }

        int x0 = coordinates[0][0];
        int y0 = coordinates[0][1];
        int x1 = coordinates[1][0];
        int y1 = coordinates[1][1];

        int dx = x1 - x0;
        int dy = y1 - y0;

        for (int i = 2; i < coordinates.length; i++) {
            int xi = coordinates[i][0];
            int yi = coordinates[i][1];

            // Check if (y_i - y_0) * (x_1 - x_0) == (y_1 - y_0) * (x_i - x_0)
            // which is (yi - y0) * dx == dy * (xi - x0)
            if (dy * (xi - x0) != dx * (yi - y0)) {
                return false;
            }
        }

        return true;
    }
}
```
### Algorithm
- 1. If `coordinates.length <= 2`, return `true`.
- 2. Select the first two points `p0(x0, y0)` and `p1(x1, y1)` as reference points.
- 3. Calculate the initial differences `dx = x1 - x0` and `dy = y1 - y0`.
- 4. Iterate through the rest of the points `pi(xi, yi)` starting from the third point (`i = 2`).
- 5. For each point `pi`, check if it satisfies the cross-multiplication equation: `dy * (xi - x0) != dx * (yi - y0)`.
- 6. If the equation is not satisfied for any point, it means the point is not on the line defined by `p0` and `p1`. Return `false`.
- 7. If the loop completes, all points are collinear. Return `true`.

# Solutions
### Java

```java
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 ; } }
```

### CPP

```cpp
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 ; } };
```

### Python

```python
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
```