Solution: Check If It Is a Straight Line

Statement

You are given an array, coordinates, where each element in coordinates[i] $= [x, y]$ represents the coordinates of a point on a $\text{2D}$ plane. Determine whether all the points in the array lie on a single straight line in the XY plane.

Constraints:

• $2 \leq$ coordinates.length $\leq 1000$

• coordinates[i].length $== 2$

• $-10^4 \leq$ coordinates[i][0], coordinates[i][1] $\leq 10^4$

• coordinates do not contain any duplicate points.

Solution

We need to determine whether a given array of coordinates in a $\text{2D}$ plane lies in a single straight line. This problem is approached using the Math and Geometry pattern, using the slope of a straight line.

Key intuition:

The slope represents the change in $\text{y-coordinates}$ relative to the change in $\text{x-coordinates}$ for any two points on the line. So, the slope between two points, $(x_1,y_1)$ and $(x_2,y_2)$, is defined as:

$\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\text{slope}=\dfrac{ΔY}{ΔX}=\dfrac{y_2−y_1}{x_2−x_1}$

To simplify the solution and reduce the computational overhead of checking the slope property for all points, we can fix the first point as a reference and compute the slopes between this reference point and all other points instead of checking all possible pairs of points.

For example: If we have points ${P_0}$, ${P_1}$, and $P_2$; the slope of the line between $P_0$ and $P_1$ is $\dfrac{ΔY_1}{ΔX_1}$. Also, the slope between $P_0$ and the subsequent point $P_2$ is $\dfrac{ΔY_2}{ΔX_2}$. So, for the points, ${P_0}$, ${P_1}$ and $P_2$ to lie in the straight line, they should have equal slopes, i.e. $\dfrac{ΔY_1}{ΔX_1} = \dfrac{ΔY_2}{ΔX_2}$. If these slopes match, the points lie in a straight line; otherwise not.

Let’s understand this with the help of a visualization: