#1232

Easy

LeetCode Problem Workspace

Check If It Is a Straight Line

Determine if a series of coordinates form a straight line on a 2D plane using geometry and mathematical principles.

Problem Statement

You are given an array of coordinates where each element is a pair representing a point in the 2D plane. Your task is to determine if all the points lie on a single straight line.

To solve the problem, you can calculate the slope between consecutive points and check if all the slopes are the same. If they are, the points form a straight line.

Examples

Example 1

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

Output: true

Example details omitted.

Example 2

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

Output: false

Example details omitted.

Constraints

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

Solution Approach

Calculate the Slope Between Points

To check if the points are collinear, calculate the slope between the first two points. The slope between two points (x1, y1) and (x2, y2) is given by (y2 - y1) / (x2 - x1). For the points to be on a straight line, the slope between each consecutive pair must be the same.

Use Cross Product to Avoid Division

To avoid division by zero and floating-point precision issues, use the cross product. For every consecutive pair of points, check if the cross product of the differences in x and y coordinates is zero. This method ensures accuracy without needing to compute actual slopes.

Edge Case Handling

If there are only two points, they always form a straight line. This edge case can be handled early in the solution to optimize performance. If the input array contains exactly two points, return true immediately.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time complexity is O(n) since we only need to iterate through the points once to check the slope or cross product. The space complexity is O(1) as we only use a constant amount of extra space.

What Interviewers Usually Probe

Candidate uses efficient math methods like slope or cross product to solve the problem.
The solution handles edge cases, especially when there are only two points.
Candidate explains the approach clearly, demonstrating understanding of geometry and array handling.

Common Pitfalls or Variants

Common pitfalls

Overlooking the edge case of two points, which should always return true.
Using division to calculate slopes, which can lead to precision issues or division by zero.
Failing to consider all points in the array when checking for collinearity.

Follow-up variants

Modify the problem to check for a straight line in 3D space using an additional z-coordinate.
Ask the candidate to find if the points form a curve or parabola instead of a straight line.
Extend the problem to handle multiple line segments and check if they form a continuous straight line.

FAQ

How can I determine if the points form a straight line?

You can check if the slopes between consecutive points are the same or use the cross product to avoid precision issues.

What if there are only two points?

Any two points always form a straight line, so you can immediately return true in this case.

Is it necessary to calculate the slope between every point?

You can optimize by using the cross product between points, which avoids floating-point issues and division by zero.

Can this problem be solved in less than O(n) time?

No, since you need to check all points at least once, the time complexity cannot be reduced below O(n).

How does GhostInterview help with solving math-based problems?

GhostInterview ensures you are aware of the most efficient techniques, like the cross product, and helps you avoid common mistakes in math-heavy questions.

terminal

Solution

Solution 1: Mathematics

The time complexity is $O(n)$, where $n$ is the length of the `coordinates` array. The space complexity is $O(1)$.

1

2

3

4

5

6

7

8

class Solution:
    def checkStraightLine(self, coordinates: List[List[int]]) -> bool:
        x1, y1 = coordinates[0]
        x2, y2 = coordinates[1]
        for x, y in coordinates[2:]:
            if (x - x1) * (y2 - y1) != (y - y1) * (x2 - x1):
                return False
        return True

Continue Practicing

#1266 minimum time visiting all points #1037 valid boomerang #1030 matrix cells in distance order