1232. Check If It Is a Straight Line

Problem Description

The problem presents us with an array called coordinates. Each element within this array is itself an array that represents a point in the form [x, y]—where x is the x-coordinate and y is the y-coordinate of a point on the XY plane. The task is to determine if all these points lie on a single straight line or not.

Intuition

To check if points lie on the same straight line, we need to ensure that the slope between any two points is the same across all points. The slope is a measure of how steep a line is. If pairs of points have different slopes, the points do not lie on a single straight line.

To calculate the slope between two points (x1, y1) and (x2, y2), we use the formula slope = (y2 - y1) / (x2 - x1). If the slope is consistent between consecutive points, then all the points are on the same line.

In our solution, we take the first two points from coordinates to calculate a reference slope. For computational efficiency and to avoid the potential division by zero error, we check the equality of slopes using a cross-multiplication method. Specifically, instead of directly computing (y2 - y1) / (x2 - x1) == (y - y1) / (x - x1), we check if (x - x1) * (y2 - y1) == (y - y1) * (x2 - x1) for subsequent points (x, y).

If the equality holds for all pairs of points in the coordinates array, the function returns True, which means all points lie on a single straight line. If any pair of points fails the equality test, the function returns False, and we know that not all points are on the same line.

The intuition behind this approach is that we're using the properties of slopes in a way that's computationally efficient and avoids possible arithmetic errors when dealing with real numbers.

Learn more about Math patterns.

Solution Approach

The algorithm follows a straightforward approach by checking if the slope between any two points is the same across all points. No additional data structures or complex patterns are necessary. The algorithm involves simple arithmetic operations and a for loop. Here's a step-by-step implementation break down:

The algorithm starts by storing the x and y coordinates of the first two points from the coordinates array in x1, y1 and x2, y2. These two points are used to find the reference slope for the line.
The algorithm then iterates over the remaining points in coordinates, starting from the third point, using a for x, y in coordinates[2:]: loop.
Inside the loop, for each point (x, y), the algorithm checks if the cross-product of the differences in coordinates between point (x, y) and the first point (x1, y1) equals the cross-product of the differences between the second point (x2, y2) and the first point.

The check is made using the following condition:
```
if (x - x1) * (y2 - y1) != (y - y1) * (x2 - x1):
    return False
```
This expression is derived from the slope equality slope1 = slope2. Instead of dividing the differences, which can cause a division by zero, it multiplies the opposite sides and compares them for equality.
If the check fails for any point, the function immediately returns False, indicating that the points do not all lie on the same straight line.
If the loop completes without encountering any point that fails the slope check, the function returns True, signaling that all points do indeed lie on a straight line.

The time complexity of this algorithm is O(n), where n is the number of points, since we have to check the condition for each point once. The space complexity is O(1) since we are using a fixed amount of additional space regardless of the number of points.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's walk through a small example to illustrate the solution approach:

Suppose coordinates = [[1, 2], [2, 3], [3, 4]]. We are looking to confirm whether these points fall on a single straight line.

Based on our algorithm, we first take the coordinates of the first two points to calculate the reference slope. So from our coordinates, we have x1, y1 = 1, 2 and x2, y2 = 2, 3.
Next, the algorithm will iterate over the remaining points in coordinates. Since we only have three points in this example, it will iterate over just one point: [3, 4].
Now, the algorithm will check if the cross-product of differences with the new point [3, 4], denoted as (x, y), and the first point (x1, y1) equals the cross-product of the differences between the second point (x2, y2) and the first point. This equation looks like:

if (3 - 1) * (3 - 2) != (4 - 2) * (2 - 1):

Simplifying the expressions on each side of the inequality gives:

if 2 * 1 != 2 * 1:

In this case, both sides are equal, meaning that the slope between point [1, 2] and point [3, 4] is the same as the slope between point [1, 2] and point [2, 3].
Since there are no more points to check, and the equality held true for the third point, the algorithm would return True.
This confirms that all the given points in the example line [1, 2], [2, 3], [3, 4] are on the same straight line.

If we had a point that did not satisfy the slope equality, for example [4, 5] replaced by [4, 6], the algorithm would compare:

if (4 - 1) * (3 - 2) != (6 - 2) * (2 - 1):

which simplifies to:

if 3 != 4:

This inequality is true, indicating that the point [4, 6] does not lie on the same straight line as the others, so the algorithm would return False.

Solution Implementation

1from typing import List
2
3class Solution:
4    def checkStraightLine(self, coordinates: List[List[int]]) -> bool:
5        # Extract the first 2 points
6        first_point = coordinates[0]
7        second_point = coordinates[1]
8      
9        # Coordinates of the first point
10        x1, y1 = first_point
11      
12        # Coordinates of the second point
13        x2, y2 = second_point
14      
15        # Check if the subsequent points are in a straight line
16        for point in coordinates[2:]:
17            x, y = point
18          
19            # Use the cross product to determine if three points are on the same line:
20            # (x - x1)/(x2 - x1) should be equal to (y - y1)/(y2 - y1)
21            # Cross-multiplying to avoid division (to handle the case when x2 - x1 is 0) we get:
22            # (x - x1) * (y2 - y1) should be equal to (y - y1) * (x2 - x1)
23            # If they are not equal for any point, the points do not form a straight line
24            if (x - x1) * (y2 - y1) != (y - y1) * (x2 - x1):
25                return False
26              
27        # If the loop completes without returning False, all points are in a straight line
28        return True
29

1class Solution {
2
3    /**
4     * Checks if all the given points lie on a straight line.
5     * 
6     * @param coordinates Array of point coordinates on a 2D plane.
7     * @return true if all points lie on a single straight line, false otherwise.
8     */
9    public boolean checkStraightLine(int[][] coordinates) {
10        // Coordinates of the first point
11        int x1 = coordinates[0][0];
12        int y1 = coordinates[0][1];
13      
14        // Coordinates of the second point
15        int x2 = coordinates[1][0];
16        int y2 = coordinates[1][1];
17      
18        // Loop over the rest of the points starting from the third one
19        for (int i = 2; i < coordinates.length; i++) {
20            // Coordinates of the current point
21            int currentX = coordinates[i][0];
22            int currentY = coordinates[i][1];
23          
24            // Check if the current point lies on the line formed by the first two points
25            // This is done by using the cross product which should be zero for collinear points
26            int deltaX1 = currentX - x1;
27            int deltaY1 = y2 - y1;
28            int deltaY2 = currentY - y1;
29            int deltaX2 = x2 - x1;
30          
31            // If current point does not satisfy the line equation then return false
32            if (deltaX1 * deltaY1 != deltaY2 * deltaX2) {
33                return false;
34            }
35        }
36      
37        // If all the points satisfy the line equation then return true
38        return true;
39    }
40}
41

1#include<vector> // Needed to use std::vector
2using std::vector;
3
4class Solution {
5public:
6    // Function to check if all points lie on a straight line.
7    bool checkStraightLine(vector<vector<int>>& coordinates) {
8        // Extract the first point (x1,y1)
9        int x1 = coordinates[0][0], y1 = coordinates[0][1];
10        // Extract the second point (x2,y2)
11        int x2 = coordinates[1][0], y2 = coordinates[1][1];
12      
13        // Loop through all the remaining points
14        for (int i = 2; i < coordinates.size(); ++i) {
15            // Extract the current point (x,y)
16            int x = coordinates[i][0], y = coordinates[i][1];
17          
18            // Check if the cross product of the vectors is zero
19            // This is a vector algebra way of checking colinearity:
20            // (x-x1)/(x2-x1) should be equal to (y-y1)/(y2-y1) for all points on the line
21            // By cross-multiplying to avoid division (and potential division by zero),
22            // we get (x-x1)*(y2-y1) == (y-y1)*(x2-x1)
23            if ((x - x1) * (y2 - y1) != (y - y1) * (x2 - x1)) {
24                return false; // The current point doesn't lie on the straight line defined by the first two points
25            }
26        }
27        // All points lie on the same straight line
28        return true;
29    }
30};
31

1// Necessary import statement when working with arrays in TypeScript
2import { Vector } from 'prelude-ts';
3
4// Function to check if all points lie on a straight line.
5function checkStraightLine(coordinates: number[][]): boolean {
6    // Extract the first point (x1, y1)
7    const x1 = coordinates[0][0];
8    const y1 = coordinates[0][1];
9  
10    // Extract the second point (x2, y2)
11    const x2 = coordinates[1][0];
12    const y2 = coordinates[1][1];
13  
14    // Loop through all the remaining points
15    for (let i = 2; i < coordinates.length; i++) {
16        // Extract the current point (x, y)
17        const x = coordinates[i][0];
18        const y = coordinates[i][1];
19      
20        // Check if the cross product of the vectors is zero
21        // This is a vector algebra way of checking collinearity:
22        // (x-x1)/(x2-x1) should be equal to (y-y1)/(y2-y1) for all points on the line
23        // By cross-multiplying to avoid division (and potential division by zero),
24        // we get (x-x1) * (y2-y1) == (y-y1) * (x2-x1)
25        if ((x - x1) * (y2 - y1) !== (y - y1) * (x2 - x1)) {
26            return false; // The current point doesn't lie on the straight line defined by the first two points
27        }
28    }
29
30    // All points lie on the same straight line
31    return true;
32}
33

Time and Space Complexity

Time Complexity

The time complexity of the function checkStraightLine is O(n), where n is the number of coordinate points in the input list coordinates. This is because the function uses a single loop that iterates through the coordinates starting from the third element, and for each iteration, it performs a constant number of mathematical operations to check if the points lie on the same line. These operations do not depend on the size of the input other than the fact that they iterate once for each element beyond the first two.

Space Complexity

The space complexity of the function is O(1). The function uses a fixed amount of extra space to store the variables x1, y1, x2, y2, x, and y. The amount of space used does not scale with the size of the input list, meaning that the space usage is constant.

Learn more about how to find time and space complexity quickly using problem constraints.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Consider the classic dynamic programming of longest increasing subsequence:

Find the length of the longest subsequence of a given sequence such that all elements of the subsequence are sorted in increasing order.

For example, the length of LIS for [50, 3, 10, 7, 40, 80] is 4 and LIS is [3, 7, 40, 80].

What is the recurrence relation?

dp[i] = dp[i] + 1

dp[i] = dp[i] + dp[i - 1]

dp[i] = (dp[i] + dp[j] + 1) for j in 0 to i

dp[i] = max(dp[i], dp[j] + 1) for j in 0 to i

I don't know