Check If It Is a Straight Line

Problem Statement:-

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.

Link: https://leetcode.com/problems/check-if-it-is-a-straight-line/

Problem Explanation with examples:-

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.

Intuition:-

• The slope of any two points in a straight line is the same. For all points to be in a straight line, the slope of any two points should be the same.

• So, we can move on considering 3 points at a time and check if the slope of all the adjacent points is the same.

• If the slope of any two points is different, then the points are not in a straight line. So, we return False.

Solution:-

• We iterate over the given points using a for loop and consider 3 points at a time by using the range of the for loop as range(len(coordinates)-2).

• We store the coordinates of the 3 points in ax,ay,bx,by,cx,cy.

• Perform the base case check for any denominator being 0 while calculating the slope. If any of the denominators is 0, then we check if the other denominator is also 0. If not, then we return False. Else, we continue with the next iteration.

• If the slope of any two points is different, then we return False. The slope is calculated as (y2 - y1)/(x2 - x1).

• If all the slopes are the same, then we return True at the end of the for loop.

Code:-

JAVA Solution

class Solution {
    public boolean checkStraightLine(int[][] coordinates) {
        for (int i = 0; i < coordinates.length - 2; i++) {
            int ax = coordinates[i][0];
            int ay = coordinates[i][1];
            int bx = coordinates[i + 1][0];
            int by = coordinates[i + 1][1];
            int cx = coordinates[i + 2][0];
            int cy = coordinates[i + 2][1];

            if ((cx - bx) == 0 || (bx - ax) == 0) {
                if ((cx - bx) != (bx - ax)) {
                    return false;
                } else {
                    continue;
                }
            }

            if (((double)(cy - by) / (cx - bx)) != ((double)(by - ay) / (bx - ax))) {
                return false;
            }
        }

        return true;
    }
}

Python Solution

class Solution:
    def checkStraightLine(self, coordinates: List[List[int]]) -> bool:
        for i in range(len(coordinates)-2):
            ax,ay = coordinates[i][0],coordinates[i][1]
            bx,by = coordinates[i+1][0],coordinates[i+1][1]
            cx,cy = coordinates[i+2][0],coordinates[i+2][1]
            if ((cx-bx) == 0 or (bx-ax) == 0):
                if (cx-bx) != (bx-ax):
                    return False
                else:
                    continue
            if ((cy-by)/(cx-bx)) != ((by-ay)/(bx-ax)):
                return False
        return True

Complexity Analysis:-

TIME:-

The time complexity is O(n), where n is the number of coordinates. The code iterates over each coordinate in the given list, performing a constant number of operations for each coordinate.

SPACE:-

The space complexity is O(1). It does not use any additional data structures that scale with the input size. Only a constant amount of space is required to store the variables and perform the computations.

References:-

• Maths

Connect with me:-

• Twitter

• Github

• LinkedIn