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.
1public class Solution {
2 public bool CheckStraightLine(int[][] coordinates) {
3 int x1 = coordinates[0][0], y1 = coordinates[0][1];
4 int x2 = coordinates[1][0], y2 = coordinates[1][1];
5 for (int i = 2; i < coordinates.Length; i++) {
6 int x = coordinates[i][0], y = coordinates[i][1];
7 if ((y2 - y1) * (x - x1) != (y - y1) * (x2 - x1)) {
8 return false;
9 }
10 }
11 return true;
12 }
13}This C# solution iterates over the array, utilizing the cross multiplication technique to avoid floating point arithmetic mistake, thus determining line 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
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 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.