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.To solve #1232 Check If It Is a Straight Line, the key idea is to verify whether all given coordinates share the same slope. If multiple points lie on a straight line, the slope between any pair of points must remain constant. Start by calculating the slope using the first two points. Then compare it with the slope formed by each subsequent point and the first point.
Instead of directly dividing values to compute the slope, a safer technique is cross multiplication. By checking whether (y2 - y1) * (x3 - x1) == (y3 - y1) * (x2 - x1), you avoid floating‑point precision issues and division by zero when vertical lines appear.
You iterate through all coordinates and confirm that this relationship holds for every point. If any comparison fails, the points do not lie on the same line. This approach is efficient because it processes each point once, resulting in O(n) time complexity and O(1) extra space.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Slope comparison using cross multiplication | O(n) | O(1) |
Techdose
Use these hints if you're stuck. Try solving on your own first.
If there're only 2 points, return true.
Check if all other points lie on the line defined by the first 2 points.
Use cross product to check collinearity.
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.
Time Complexity: O(n), where n is the number of points.
Space Complexity: O(1), as we use a fixed number of extra variables.
1#include <stdbool.h>
2
3bool checkStraightLine(int** coordinates, int coordinatesSize, int* coordinatesColSize) {
4 int x1 = coordinates[0][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.
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.
Time Complexity: O(n), where n refers to the number of coordinates.
Space Complexity: O(1), as only constant additional space is used.
1 public bool CheckStraightLine(int[][] coordinates) {
int dx = coordinates[1][0] - coordinates[0][0];
int dy = coordinates[1][1] - coordinates[0][1];
for (int i = 2; i < coordinates.Length; i++) {
int x = coordinates[i][0] - coordinates[0][0];
int y = coordinates[i][1] - coordinates[0][1];
if (dx * y != dy * x) return false;
}
return true;
}
}Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, geometry and coordinate-based problems like this occasionally appear in coding interviews. While it is an easy-level problem, interviewers may use it to test mathematical reasoning, edge case handling, and clean implementation.
No special data structure is required for this problem. The coordinates are already provided in an array, and a simple iteration through the points is enough to validate the line condition.
The optimal approach is to verify that the slope between the first two points matches the slope formed with every other point. Instead of dividing, use cross multiplication to compare slopes. This avoids precision issues and works well even for vertical lines.
Directly calculating slopes using division can introduce floating-point precision errors and fails when the denominator is zero. Cross multiplication compares slopes using integer arithmetic, making the check more reliable and safe.
This C# strategy approaches line determination via vector subtraction followed by cross product stability checks between consecutive coordinates. It's directly computed without coordinate division.