Check If It Is A Straight Line - Leetcode Solution

Problem:

You are given an array coordinates, where coordinates[i] = [x, y] represents the coordinate of a point. Check if these points make a straight line in the XY plane.

Solution:

We need to check if all the points given in the coordinates array lie on the same straight line or not. We can use the slope between any two points to check if they lie on the same line or not.

To calculate the slope between two points, we use the formula,

slope = (y2 - y1) / (x2 - x1)

We take two points at a time and calculate the slope between those points. If we find that the slope between any two points is not equal to the slope between the first two points, then we can say that all the points do not lie on the same straight line.

If the slopes between all the points are equal, then all the points must lie on the same straight line. The only exception to this rule is when the line is vertical, in which case the slope is undefined. In this case, we need to check if all the points have the same value for x.

Let us look at the implementation of this solution in Python:

class Solution:
    def checkStraightLine(self, coordinates: List[List[int]]) -> bool:
        if len(coordinates) == 2:
            return True
        
        # Calculate the slope between the first two points
        x1, y1 = coordinates[0]
        x2, y2 = coordinates[1]
        slope = (y2 - y1) / (x2 - x1)
        
        # Check all the other points
        for i in range(2, len(coordinates)):
            x1, y1 = coordinates[i-1]
            x2, y2 = coordinates[i]
            
            # If the line is vertical, check if all the points have the same x value
            if x2 - x1 == 0:
                if x1 != x2:
                    return False
            else:
                # Calculate the slope between the current points
                curr_slope = (y2 - y1) / (x2 - x1)
                
                # If the slopes are different, points don't lie on the same line
                if curr_slope != slope:
                    return False
                
        return True

Time Complexity: O(n), where n is the number of points given in the coordinates array.

Space Complexity: O(1), as we are not using any extra space in the algorithm.

1