Check If It Is a Straight Line

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

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.

1public class Solution {2    public boolean checkStraightLine(int[][] coordinates) {3        if (coordinates.length <= 2) {4            return true;5        }6 7        int x0 = coordinates[0][0];8        int y0 = coordinates[0][1];9        int x1 = coordinates[1][0];10        int y1 = coordinates[1][1];11 12        // Handle vertical line case13        if (x1 - x0 == 0) {14            for (int i = 2; i < coordinates.length; i++) {15                if (coordinates[i][0] != x0) {16                    return false;17                }18            }19            return true;20        }21 22        // Calculate the reference slope23        double slope = (double)(y1 - y0) / (x1 - x0);24 25        // Check the slope for all other points26        for (int i = 2; i < coordinates.length; i++) {27            int xi = coordinates[i][0];28            int yi = coordinates[i][1];29            // Handle the case where the current pair of points form a vertical line30            if (xi - x0 == 0) {31                return false; // Since the main line is not vertical32            }33            double currentSlope = (double)(yi - y0) / (xi - x0);34            if (currentSlope != slope) {35                return false;36            }37        }38 39        return true;40    }41}

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

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.

1public class Solution {2    public boolean checkStraightLine(int[][] coordinates) {3        if (coordinates.length <= 2) {4            return true;5        }6 7        int x0 = coordinates[0][0];8        int y0 = coordinates[0][1];9        int x1 = coordinates[1][0];10        int y1 = coordinates[1][1];11 12        int dx = x1 - x0;13        int dy = y1 - y0;14 15        for (int i = 2; i < coordinates.length; i++) {16            int xi = coordinates[i][0];17            int yi = coordinates[i][1];18 19            // Check if (y_i - y_0) * (x_1 - x_0) == (y_1 - y_0) * (x_i - x_0)20            // which is (yi - y0) * dx == dy * (xi - x0)21            if (dy * (xi - x0) != dx * (yi - y0)) {22                return false;23            }24        }25 26        return true;27    }28}