Leetcode – Check If It Is a Straight Line Solution

The “Check If It Is a Straight Line” problem on Leetcode is a compelling problem that involves applying basic geometric concepts in a programming context. Specifically, it tests your ability to work with coordinates, lines, and slopes in a two-dimensional space. While the problem may sound straightforward, its real challenge lies in ensuring that your solution is not just correct but also efficient. In this detailed article, we’ll delve into the problem statement, explore various solution approaches, examine their time and space complexities, and look at Python code implementations.

Problem Statement

Description

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.

Constraints

• 2 <= coordinates.length <= 1000
• coordinates[i].length == 2
• -10^4 <= coordinates[i][0], coordinates[i][1] <= 10^4
• coordinates contains no duplicate point.

Understanding the Problem

The problem requires you to determine whether a given set of points lies on a straight line. In geometry, points lie on a straight line if the slope between any two points is the same. The formula for calculating the slope between two points (x1,y1) and (x2,y2) is:

Your task is to implement this in code and check if all points have the same slope, implying they lie on a straight line.

Approaches

Approach 1: Calculating Slope for All Points

The most intuitive approach is to calculate the slope between each pair of points and ensure they are all the same.

Algorithm

1. Take the first two points and calculate the slope.
2. Loop through the remaining points, calculating the slope between the current and the first point.
3. Compare the calculated slope with the initial slope. If any slope differs, return False.
4. If the loop completes successfully, return True.

Python Code Implementation

def check_straight_line(coordinates):
    (x1, y1), (x2, y2) = coordinates[:2]
    initial_slope = (y2 - y1) / (x2 - x1) if x2 != x1 else None
    
    for i in range(2, len(coordinates)):
        x, y = coordinates[i]
        slope = (y - y1) / (x - x1) if x != x1 else None
        if slope != initial_slope:
            return False
    return True

# Test the function
print(check_straight_line([[1, 2], [2, 3], [3, 4]]))  # Output should be True
print(check_straight_line([[1, 1], [3, 2], [5, 3], [7, 4]]))  # Output should be True
print(check_straight_line([[1, 1], [3, 2], [5, 3], [7, 5]]))  # Output should be False

Time Complexity

This approach has a time complexity of O(n), where n is the number of coordinates.

Space Complexity

The space complexity is O(1) as we use constant space apart from the input array.

Approach 2: Optimized Slope Calculation

We can optimize the slope calculation by avoiding division, which also helps us to prevent any floating-point errors. To check whether the slopes between three points (x1,y1), (x2,y2), and (x3,y3) are equal, we can use the following equation:

Algorithm

1. Calculate (y2−y1)×(x3−x1) and (y3−y1)×(x2−x1).
2. Compare these values for all points.

Python Code Implementation

def check_straight_line(coordinates):
    (x1, y1), (x2, y2) = coordinates[:2]
    
    for i in range(2, len(coordinates)):
        x, y = coordinates[i]
        if (y2 - y1) * (x - x1) != (y - y1) * (x2 - x1):
            return False
    return True

# Test the function
print(check_straight_line([[1, 2], [2, 3], [3, 4]]))  # Output should be True
print(check_straight_line([[1, 1], [3, 2], [5, 3], [7, 4]]))  # Output should be True
print(check_straight_line([[1, 1], [3, 2], [5, 3], [7, 5]]))  # Output should be False

Time Complexity

This approach also has a time complexity of O(n).

Space Complexity

The space complexity remains O(1).

Conclusion

The “Check If It Is a Straight Line” problem serves as an excellent entry point for combining geometric concepts with programming logic. We explored two different approaches: the first straightforwardly calculates slopes, while the second optimizes this process by avoiding division. Both methods have the same time complexity O(n) and constant space complexity O(1), but the second method offers the advantage of avoiding floating-point arithmetic, thus being more reliable for this particular problem.