Problem Statement
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
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 <= 1000
coordinates[i].length == 2
-10^4 <= coordinates[i][0], coordinates[i][1] <= 10^4
-
coordinates
contains no duplicate point.
Solution Thought Process
Let's solve a simple problem first. We are given 3 coordinates (x1, y1)
, (x2,y2)
, (x3,y3)
. We are told to find if those 3 points form a line. What we would do is, find the tangent of those points and compare them. If they are the same, then we can say that the lines are equal.
Say the three points are (0,2)
, (10,14)
, (30,38)
So we can say that those points form a line.
Following this mathematical formula, we can scan all the points in the array, considering only two at a time. For reducing the complexity of the floating division, we will separate the tangent into two parts - numerator and denominator. For example, in the above formula, numerator = 6
and denominator = 5
.
- First, we find the numerator for those two points (the difference between y coordinates).
- We find the denominator for those two points (the difference between x coordinates).
- We find the gcd of numerator and denominator.
- We divide numerator and denominator by gcd to get the co-prime form for comparing. For comparing the tangents, we have to reduce them into their co-prime form.
- If it's the first element and the second element in the array, then we store the numerator and denominator in a separate value.
For the further elements, we have to check the numerator and the denominator with the previously-stored numerator and denominator of the tangent. If they don't match, we return false.
If every tangent matches with each other, then we return true. Those points do form a line, indeed!
Solution
class Solution {
public:
bool checkStraightLine(vector<vector<int>>& coordinates) {
int tangent_numerator = -1, tangent_denominator = -1;
for(int i=0;i<coordinates.size()-1;i++)
{
int numerator = abs(coordinates[i][1] - coordinates[i+1][1]);
int denominator = abs(coordinates[i][0] - coordinates[i+1][0]);
int gcd = __gcd(numerator, denominator);
numerator /= gcd;
denominator /= gcd;
if(i==0)
{
tangent_numerator = numerator;
tangent_denominator = denominator;
}
else
{
if(numerator != tangent_numerator || denominator != tangent_denominator)
{
return false;
}
}
}
return true;
}
};
Complexity
Time Complexity: O(n), we are just iterating over the points.
Space Complexity: O(1).
Top comments (0)