Problem Description

You are given an array of points in a 2D plane where each point is represented as [x, y] coordinates. Your task is to determine whether all these points lie on the same straight line.

The input coordinates is an array where coordinates[i] = [x, y] represents the x and y coordinates of the i-th point. You need to check if all points in the array form a straight line when plotted on an XY plane and return true if they do, false otherwise.

The solution uses the mathematical property that three points (x1, y1), (x2, y2), and (x, y) are collinear (lie on the same line) if and only if the cross product of vectors from the first point to the other two points equals zero. This is expressed as: (x - x1) * (y2 - y1) = (y - y1) * (x2 - x1).

The algorithm takes the first two points as reference points to define the line, then checks if every subsequent point satisfies the collinearity condition with these two reference points. If any point fails this check, the points don't form a straight line. This approach avoids division operations and handles vertical lines naturally by using cross multiplication instead of calculating slopes directly.

Intuition

When we need to check if points form a straight line, the first thought might be to calculate the slope between consecutive points and verify they're all equal. The slope between two points (x1, y1) and (x2, y2) is (y2 - y1) / (x2 - x1).

However, this approach has a problem: division by zero when dealing with vertical lines (when x2 - x1 = 0). We'd need special case handling for vertical lines, making the code more complex.

To avoid division altogether, we can rearrange the slope equality check. If three points are on the same line, the slope from point 1 to point 2 should equal the slope from point 1 to point 3:

(y2 - y1) / (x2 - x1) = (y3 - y1) / (x3 - x1)

By cross-multiplying to eliminate the fractions, we get:

(y2 - y1) * (x3 - x1) = (y3 - y1) * (x2 - x1)

This elegant transformation removes division entirely, naturally handles vertical lines, and avoids floating-point precision issues. We simply pick the first two points as our reference line, then verify that every other point maintains this same relationship. If any point breaks this pattern, we know the points don't all lie on the same straight line.

Learn more about Math patterns.

Solution Approach

The implementation follows a straightforward approach using the cross-multiplication formula we derived:

1. Extract Reference Points: First, we take the first two points from the coordinates array as our reference points (x1, y1) and (x2, y2). These two points define the line that all other points should lie on.

2. Iterate Through Remaining Points: Starting from the third point (index 2), we iterate through all remaining points in the array. For each point (x, y), we need to verify it's collinear with our reference points.

3. Apply Collinearity Check: For each point (x, y), we check the condition:

   (x - x1) * (y2 - y1) != (y - y1) * (x2 - x1)

   If this inequality is true, it means the current point doesn't lie on the same line as the reference points, so we immediately return False.

4. Return Result: If we successfully check all points without finding any that break the collinearity condition, we return True, confirming all points form a straight line.

The algorithm has a time complexity of O(n) where n is the number of points, as we check each point exactly once. The space complexity is O(1) since we only use a constant amount of extra variables regardless of input size.

This approach elegantly handles all edge cases including vertical lines, horizontal lines, and diagonal lines without any special case handling, making it both efficient and robust.

Example Walkthrough

Let's walk through the solution with a concrete example to see how the algorithm works.

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

Let's check if these points form a straight line.

Step 1: Extract Reference Points

• First point (x1, y1) = (1, 2)
• Second point (x2, y2) = (2, 3)
• These two points define our reference line

Step 2: Check Each Remaining Point

For point at index 2: [3, 4] where (x, y) = (3, 4)

• Calculate left side: (x - x1) * (y2 - y1) = (3 - 1) * (3 - 2) = 2 * 1 = 2
• Calculate right side: (y - y1) * (x2 - x1) = (4 - 2) * (2 - 1) = 2 * 1 = 2
• Since 2 == 2, this point is collinear ✓

For point at index 3: [4, 5] where (x, y) = (4, 5)

• Calculate left side: (x - x1) * (y2 - y1) = (4 - 1) * (3 - 2) = 3 * 1 = 3
• Calculate right side: (y - y1) * (x2 - x1) = (5 - 2) * (2 - 1) = 3 * 1 = 3
• Since 3 == 3, this point is collinear ✓

Result: All points satisfy the collinearity condition, so we return True.

These points indeed form a straight line with slope 1 (each x increases by 1, each y increases by 1).

Counter-example: If we had coordinates = [[1,2], [2,3], [3,5]]

• For the third point [3, 5]:
• Left side: (3 - 1) * (3 - 2) = 2 * 1 = 2
• Right side: (5 - 2) * (2 - 1) = 3 * 1 = 3
• Since 2 != 3, this point is NOT collinear, we'd return False

Solution Implementation

Time and Space Complexity

The time complexity is O(n), where n is the length of the coordinates array. This is because the algorithm iterates through the coordinates array once, starting from index 2, performing a constant-time operation (the cross-product calculation (x - x1) * (y2 - y1) != (y - y1) * (x2 - x1)) for each point. Since we examine n - 2 points after the first two reference points, and each check takes O(1) time, the overall time complexity is O(n).

The space complexity is O(1). The algorithm only uses a fixed amount of extra space to store the coordinates of the first two points (x1, y1, x2, y2) and the loop variables (x, y). No additional data structures are created that scale with the input size, so the space usage remains constant regardless of how many coordinates are in the input array.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Division by Zero When Using Slope Formula

One of the most common mistakes when solving this problem is attempting to use the traditional slope formula directly:

# WRONG APPROACH - Can cause division by zero
def checkStraightLine(self, coordinates):
    x1, y1 = coordinates[0]
    x2, y2 = coordinates[1]
  
    # This fails when x2 == x1 (vertical line)
    slope = (y2 - y1) / (x2 - x1)  # Division by zero error!
  
    for x, y in coordinates[2:]:
        current_slope = (y - y1) / (x - x1)  # Another potential division by zero
        if current_slope != slope:
            return False
    return True

Why it fails: When dealing with vertical lines where x2 == x1, the denominator becomes zero, causing a runtime error.

Solution: The provided cross-multiplication approach avoids division entirely by rearranging the equation from (y2 - y1) / (x2 - x1) = (y - y1) / (x - x1) to (x - x1) * (y2 - y1) = (y - y1) * (x2 - x1).

2. Floating Point Precision Issues

Another pitfall occurs when developers try to handle the division by zero case but introduce floating-point comparisons:

# PROBLEMATIC APPROACH - Floating point precision issues
def checkStraightLine(self, coordinates):
    x1, y1 = coordinates[0]
    x2, y2 = coordinates[1]
  
    for x, y in coordinates[2:]:
        # Using division can lead to precision errors
        if (x2 - x1) != 0 and (x - x1) != 0:
            slope1 = (y2 - y1) / (x2 - x1)
            slope2 = (y - y1) / (x - x1)
            if slope1 != slope2:  # Floating point comparison can be unreliable
                return False
    return True

Why it fails: Floating-point arithmetic can introduce small rounding errors, making exact equality comparisons unreliable.

Solution: The cross-multiplication method uses only integer arithmetic (assuming integer coordinates), completely avoiding floating-point precision issues.

3. Incorrect Handling of Edge Cases

Some implementations forget to handle special cases like when all points have the same x-coordinate (vertical line) or y-coordinate (horizontal line):

# INCOMPLETE APPROACH - Missing edge case handling
def checkStraightLine(self, coordinates):
    if len(coordinates) <= 2:
        return True
  
    # Trying to handle vertical/horizontal lines separately
    if coordinates[1][0] == coordinates[0][0]:  # Vertical line
        for point in coordinates[2:]:
            if point[0] != coordinates[0][0]:
                return False
        return True
    # ... similar code for horizontal lines
    # ... then handle general case

Why it's problematic: This approach requires multiple conditional branches and separate logic for different line orientations, making the code complex and error-prone.

Solution: The cross-multiplication formula naturally handles all cases (vertical, horizontal, and diagonal lines) with a single unified approach, eliminating the need for special case handling.