LeetCode: Check If It Is a Straight Line
Tags: leetcode, algorithms, datastructures, math
Published: 2020-05-09 07:01:26

---
title: LeetCode: Check If It Is a Straight Line
published: true
description: 08.05.2020
tags: leetcode, algorithms, datastructures, math
series: LeetCode May Challenge
---

### 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:**

![img](https://assets.leetcode.com/uploads/2019/10/15/untitled-diagram-2.jpg)

```
Input: coordinates = [[1,2],[2,3],[3,4],[4,5],[5,6],[6,7]]
Output: true
```

**Example 2:**

**![img](https://assets.leetcode.com/uploads/2019/10/09/untitled-diagram-1.jpg)**

```
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.

{% katex inline %}

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

{% endkatex %}

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

{% katex inline %}

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}

{% endkatex %}

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

```c++
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).