{x}
blog image

Check If It Is a Straight Line

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:

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

Example 2:

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.

Solution Explanation: Check If It Is a Straight Line

This problem asks whether a given set of points forms a straight line. The most efficient way to solve this is by leveraging the concept of slope. If all points lie on a straight line, the slope between any two points should be the same. However, we must handle the case where the line is vertical (undefined slope).

Approach:

  1. Calculate the slope: We calculate the slope between the first two points. The slope m is given by (y2 - y1) / (x2 - x1).

  2. Handle vertical lines: If x2 - x1 is 0 (vertical line), we check if all subsequent points have the same x-coordinate as x1.

  3. Check other points: For each subsequent point, we calculate the slope with respect to the first point. If this slope is different from the initial slope m, the points don't form a straight line.

Time Complexity: O(n), where n is the number of points. We iterate through the array of coordinates once.

Space Complexity: O(1), as we use only a constant amount of extra space to store variables.

Code Implementation (Python):

class Solution:
    def checkStraightLine(self, coordinates: List[List[int]]) -> bool:
        x1, y1 = coordinates[0]
        x2, y2 = coordinates[1]
 
        # Handle vertical line case
        if x2 - x1 == 0:
            for i in range(2, len(coordinates)):
                if coordinates[i][0] != x1:
                    return False
            return True
 
        # Calculate initial slope
        m = (y2 - y1) / (x2 - x1)
 
        # Check other points
        for i in range(2, len(coordinates)):
            x, y = coordinates[i]
            if (y - y1) / (x - x1) != m:  # Check if slope is consistent
                return False
 
        return True

Code Implementation (Java):

class Solution {
    public boolean checkStraightLine(int[][] coordinates) {
        int x1 = coordinates[0][0];
        int y1 = coordinates[0][1];
        int x2 = coordinates[1][0];
        int y2 = coordinates[1][1];
 
        //Handle vertical line case
        if(x2 - x1 == 0){
            for(int i = 2; i < coordinates.length; i++){
                if(coordinates[i][0] != x1) return false;
            }
            return true;
        }
 
        double m = (double)(y2 - y1) / (x2 - x1); //Initial slope
 
        for(int i = 2; i < coordinates.length; i++){
            int x = coordinates[i][0];
            int y = coordinates[i][1];
            if((double)(y - y1) / (x-x1) != m) return false; //Check for consistent slope
 
        }
        return true;
    }
}

Code Implementation (C++):

class Solution {
public:
    bool checkStraightLine(vector<vector<int>>& coordinates) {
        int x1 = coordinates[0][0];
        int y1 = coordinates[0][1];
        int x2 = coordinates[1][0];
        int y2 = coordinates[1][1];
 
        //Handle vertical line case
        if(x2 - x1 == 0){
            for(int i = 2; i < coordinates.size(); i++){
                if(coordinates[i][0] != x1) return false;
            }
            return true;
        }
 
        double m = (double)(y2 - y1) / (x2 - x1); //Initial slope
 
        for(int i = 2; i < coordinates.size(); i++){
            int x = coordinates[i][0];
            int y = coordinates[i][1];
            if((double)(y - y1) / (x-x1) != m) return false; //Check for consistent slope
        }
        return true;
    }
};

Code Implementation (Go):

func checkStraightLine(coordinates [][]int) bool {
	x1, y1 := coordinates[0][0], coordinates[0][1]
	x2, y2 := coordinates[1][0], coordinates[1][1]
 
	//Handle vertical line case
	if x2 - x1 == 0 {
		for i := 2; i < len(coordinates); i++ {
			if coordinates[i][0] != x1 {
				return false
			}
		}
		return true
	}
 
	m := float64(y2-y1) / float64(x2-x1) //Initial slope
 
	for i := 2; i < len(coordinates); i++ {
		x, y := coordinates[i][0], coordinates[i][1]
		if float64(y-y1)/float64(x-x1) != m { //Check for consistent slope
			return false
		}
	}
	return true
}

These code examples all implement the same core algorithm, adapting the syntax to their respective languages. They all achieve a time complexity of O(n) and a space complexity of O(1). Remember to handle potential division by zero errors (vertical lines) carefully as shown in the provided solutions.