We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Check If It Is a Straight Line

Number: 1349

Difficulty: Easy

Paid? No

Companies: Datadog, Amazon, Apple, Palantir Technologies

Problem Description

Given an array of points, where each point is represented as [x, y], determine whether all the points lie on a single straight line in the XY plane.

Key Insights

  • Use the first two points to calculate the slope of the line.
  • Instead of using division (which may lead to division-by-zero issues), use cross multiplication: for any point (x, y), check if (x - x1) * (y2 - y1) equals (y - y1) * (x2 - x1).
  • This avoids floating-point precision issues and handles vertical lines seamlessly.
  • Loop through each point starting from the third, and if any point does not satisfy the condition, return false.

Space and Time Complexity

Time Complexity: O(n), where n is the number of points. Space Complexity: O(1), as we only use a few extra variables.

Solution

The solution begins by calculating the differences dx and dy using the first two points. For each subsequent point, we use cross multiplication to verify that the point aligns with the direction defined by these differences. This technique eliminates the risk of division errors and works even if the line is vertical. If any point fails this check, the function returns false; otherwise, it returns true after all points have been validated.

Code Solutions

# Function to check if all points lie on a straight line
def check_straight_line(coordinates):
    # Calculate differences using the first two points
    x0, y0 = coordinates[0]
    x1, y1 = coordinates[1]
    dx = x1 - x0
    dy = y1 - y0

    # Check each subsequent point using cross multiplication
    for x, y in coordinates[2:]:
        # If the cross product is not zero, points are not collinear
        if (x - x0) * dy != (y - y0) * dx:
            return False
    return True

# Example usage:
coordinates1 = [[1,2],[2,3],[3,4],[4,5],[5,6],[6,7]]
print(check_straight_line(coordinates1))  # Expected output: True

coordinates2 = [[1,1],[2,2],[3,4],[4,5],[5,6],[7,7]]
print(check_straight_line(coordinates2))  # Expected output: False
← Back to All Questions