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.
Example 1:
Input: coordinates = [[1,2],[2,3],[3,4],[4,5],[5,6],[6,7]] Output: true
Example 2:
Input: coordinates = [[1,1],[2,2],[3,4],[4,5],[5,6],[7,7]] Output: false
Constraints:
2 <= coordinates.length <= 1000coordinates[i].length == 2-10^4 <= coordinates[i][0], coordinates[i][1] <= 10^4coordinates contains no duplicate point.Problem Overview: You receive a list of 2D coordinates. The task is to determine whether every point lies on the same straight line. If the slope between every pair of consecutive points is identical, the points form a single line.
Approach 1: Using Slope Comparison (Time: O(n), Space: O(1))
This approach compares slopes between the first two points and every other pair of points. Compute the slope using (y2 - y1) / (x2 - x1). Instead of division, compare cross-multiplied values (y2 - y1) * (x - x1) and (y - y1) * (x2 - x1) to avoid floating point precision errors and division by zero. Iterate through the remaining coordinates and verify the slope consistency with the first segment. If any slope differs, the points do not form a straight line.
This method works well for problems involving coordinate relationships in geometry. It performs a single pass through the coordinates, so runtime is linear. Space remains constant since only a few variables store slope components.
Approach 2: Vector Cross Product (Time: O(n), Space: O(1))
A more geometric solution uses vector cross products. Form a base vector from the first two points: v = (x2 - x1, y2 - y1). For every other point, construct another vector from the first point: w = (xi - x1, yi - y1). If the cross product v.x * w.y - v.y * w.x equals zero, the vectors are collinear. Non-zero means the point deviates from the line.
This technique directly checks collinearity and avoids slope calculations entirely. It is common in computational geometry and works reliably even for vertical lines. Implementation requires only arithmetic operations while iterating once through the coordinate array. Time complexity remains O(n) with constant memory.
Recommended for interviews: Both solutions run in O(n) time and O(1) space, which is optimal because you must inspect every point. The vector cross product approach is often preferred in interviews since it avoids division and handles vertical lines naturally. Implementing slope comparison still demonstrates a strong understanding of coordinate geometry, while the cross product version signals deeper familiarity with geometric vector operations.
In this approach, we calculate the slope between the first two points and then compare this slope with that of subsequent points. The slope between two points (x1, y1) and (x2, y2) is given by (y2-y1)/(x2-x1). For all points to lie on the same line, this slope should be constant for every pair of consecutive points.
This C solution checks the constancy of slope using cross multiplication to avoid division and potential floating point precision issues. It iterates through all points starting from the third point and compares the calculated product terms for collinearity.
Time Complexity: O(n), where n is the number of points.
Space Complexity: O(1), as we use a fixed number of extra variables.
This approach uses the cross-product method which is useful for determining collinearity without explicitly calculating slopes. For every pair of consecutive vectors, compute the cross product to determine if they are collinear. If all cross products are zero, the points are collinear.
This C solution utilizes the vector cross-product to determine if any vectors are non-collinear by checking if the cross-product between consecutive points remains zero.
Time Complexity: O(n), where n refers to the number of coordinates.
Space Complexity: O(1), as only constant additional space is used.
The time complexity is O(n), where n is the length of the coordinates array. The space complexity is O(1).
| Approach | Complexity |
|---|---|
| Approach 1: Using Slope Comparison | Time Complexity: O(n), where n is the number of points. |
| Approach 2: Vector Cross Product | Time Complexity: O(n), where n refers to the number of coordinates. |
| Mathematics | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Slope Comparison | O(n) | O(1) | Simple implementation when checking slope equality across coordinates |
| Vector Cross Product | O(n) | O(1) | Preferred geometric method that avoids division and handles vertical lines safely |
Check If It Is a Straight Line | Leetcode #1232 | Find if all coordinate points form a straight line • Techdose • 20,971 views views
Watch 9 more video solutions →Practice Check If It Is a Straight Line with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor