1232. Check If It Is a Straight Line
Model: qwen2.5-coder:14b
Topics: Array,Math,Geometry
FAANG asked: 0
Acceptance rate: 43.2%
Problem Breakdown
The problem asks us to determine whether a set of given points in the XY plane lie on a straight line. The input is an array of coordinates where each coordinate is represented as [x, y]. The output should be true if all points are collinear (lie on the same straight line) and false otherwise.
Inputs:
- An array of coordinates,
coordinates[i] = [x, y].
Outputs:
- A boolean value indicating whether the points form a straight line.
Implicit Constraints or Edge Cases:
- The number of points is between 2 and 1000.
- Each coordinate is within the range
-10^4 <= x, y <= 10^4. - There are no duplicate points in the input array.
Intuition
A brute-force approach would involve checking if every pair of points has the same slope. However, this would be inefficient with a time complexity of O(n^2), which is not suitable given the constraints.
The key insight is to use the concept of slopes between points. If all points have the same slope relative to the first point, then they lie on a straight line. This can be checked using the formula for the slope between two points (x1, y1) and (x2, y2), which is (y2 - y1) / (x2 - x1). To avoid division and potential floating-point precision issues, we can use the cross-multiplication method: (y2 - y1) * (x3 - x2) == (y3 - y2) * (x2 - x1).
Approach
- Initial Check: If there are only two points, they trivially form a straight line.
- Calculate Slopes: For each subsequent point, calculate the slope using cross-multiplication to avoid division.
- Compare Slopes: Compare the calculated slopes with the slope between the first two points. If all slopes match, return
true; otherwise, returnfalse.
Complexity Analysis
- Time Complexity: O(n), where n is the number of coordinates. We iterate through the list once to check the slopes.
- Space Complexity: O(1), as we only use a constant amount of extra space for variables.
Solution
class Solution:
def checkStraightLine(self, coordinates: List[List[int]]) -> bool:
# If there are only two points, they form a straight line
if len(coordinates) == 2:
return True
# Calculate the initial slope using cross-multiplication
x1, y1 = coordinates[0]
x2, y2 = coordinates[1]
for i in range(2, len(coordinates)):
x3, y3 = coordinates[i]
# Check if the current point has the same slope as the first two points
if (y2 - y1) * (x3 - x2) != (y3 - y2) * (x2 - x1):
return False
return True
Edge Cases Handled
- Two Points: The code correctly returns
truefor two points, as they trivially form a straight line. - Vertical Lines: The cross-multiplication method avoids division by zero issues that would occur with vertical lines (where x-coordinates are the same).
- Horizontal Lines: Similarly, horizontal lines (where y-coordinates are the same) are handled correctly without any special cases.