Leetcode 1232: Check If It Is a Straight Line

Input: The input consists of a list of points, where each point is represented by two integers [x, y].

Example: coordinates = [[2, 3], [4, 5], [6, 7], [8, 9], [10, 11]]

Constraints:

• 2 <= coordinates.length <= 1000

• coordinates[i].length == 2

• -10^4 <= coordinates[i][0], coordinates[i][1] <= 10^4

• coordinates contains no duplicate point.

Output: The output should be a boolean value indicating whether all points lie on the same straight line.

Example: true

Constraints:

• Return 'true' if all points are collinear, otherwise return 'false'.

Goal: The goal is to check if the slope between consecutive points remains the same across the entire list of points.

Steps:

• Calculate the slope between the first two points.

• For each subsequent point, calculate the slope between it and the first point.

• If the slopes are not equal, return false.

• If all slopes are equal, return true.

Goal: The input list contains no duplicate points, and the size of the list is between 2 and 1000.

Steps:

• Ensure no duplicate points in the input array.

Assumptions:

• The input coordinates represent valid points in a 2D plane.

• The points are given in no particular order.

• Input: coordinates = [[2, 3], [4, 5], [6, 7], [8, 9], [10, 11]]

• Explanation: The points have the same slope between consecutive pairs, meaning they lie on the same straight line, so the output is 'true'.

• Input: coordinates = [[1, 1], [2, 3], [3, 5], [4, 7]]

• Explanation: The slope between the first two points is different from the slopes between the other points, meaning they do not lie on the same straight line, so the output is 'false'.

Approach: To determine if the points are collinear, we calculate the slope between the first point and the second, then compare it to the slope between the first point and each subsequent point.

Observations:

• The slope between two points is given by the formula (y2 - y1) / (x2 - x1).

• If the slopes between consecutive points are all equal, the points must lie on the same straight line.

Steps:

• Calculate the slope between the first two points.

• For each subsequent point, calculate the slope between it and the first point.

• If all slopes are equal, return true. Otherwise, return false.

Empty Inputs:

• Not applicable, as the input will always contain at least two points.

Large Inputs:

• The solution should handle up to 1000 points efficiently.

Special Values:

• The coordinates can include negative values, but the slope calculation remains unaffected.

Constraints:

• Ensure that there are no duplicate points in the input.

bool checkStraightLine(vector<vector<int>>& cord) {
    double slopt = (cord[1][0] - cord[0][0]) == 0? INT_MAX: (double)(cord[1][1] - cord[0][1]) / (double)(cord[1][0] - cord[0][0]);
    for(int i = 2; i < cord.size(); i++) {
        double slp = (cord[i][0] - cord[0][0]) == 0?INT_MAX: (double)(cord[i][1] - cord[0][1]) / (double)(cord[i][0] - cord[0][0]);
        if(slp != slopt) return false;
    }
    return true;
}

1 : Function Definition

bool checkStraightLine(vector<vector<int>>& cord) {

This is the function definition for `checkStraightLine`. The function takes a 2D vector of coordinates and checks whether the points lie on a straight line.

2 : Slope Calculation

    double slopt = (cord[1][0] - cord[0][0]) == 0? INT_MAX: (double)(cord[1][1] - cord[0][1]) / (double)(cord[1][0] - cord[0][0]);

The slope between the first two points is calculated. If the x-values of the points are the same, the slope is set to `INT_MAX` to represent an undefined slope (vertical line).

3 : Iteration Over Points

    for(int i = 2; i < cord.size(); i++) {

The function iterates over all the remaining points starting from the third point.

4 : Slope Comparison

        double slp = (cord[i][0] - cord[0][0]) == 0?INT_MAX: (double)(cord[i][1] - cord[0][1]) / (double)(cord[i][0] - cord[0][0]);

For each point, the slope with respect to the first point is calculated. If the x-values are the same, the slope is set to `INT_MAX`.

5 : Slope Check

        if(slp != slopt) return false;

If the calculated slope of any point does not match the slope of the first two points, the function returns `false`, indicating the points do not form a straight line.

6 : Return True

    return true;

If all slopes are the same, the function returns `true`, indicating the points form a straight line.

Best Case: O(n)

Average Case: O(n)

Worst Case: O(n)

Description: We iterate through the points exactly once, so the time complexity is O(n), where n is the number of points.

Best Case: O(1)

Worst Case: O(1)

Description: The space complexity is constant, as we only use a few variables for slope calculation.

Leetcode 1232: Check If It Is a Straight Line

Explore →