LeetCode: Check If It Is a Straight Line

#leetcode #algorithms #datastructures #math

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.

$tan1 = \frac{y1-y2}{x1-x2} \newline \newline tan2 = \frac{y2-y3}{x2-x3}$

Say the three points are (0,2), (10,14), (30,38)

$tan1 = \frac{2-14}{0-10} = \frac{-12}{-10} = \frac {6}{5} \newline \newline tan2 = \frac{14-38}{10-30} = \frac{-24}{-20} = \frac{6}{5}$

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;
    }
};