Teaching to learn: Check If It Is a Straight Line

Leetcode: Check If It is a Straight Line

This post is part of series where I will be breaking down coding problems that I have solved and sharing the lessons I learned while finding an answer. The coding language will be in JavaScript.

I hope you haven’t forgotten about all that math you learned back in school… Oh you forgot most of it because you don’t regularly use the concepts? No worries. We have THE INTERNET!

Seriously though, I had to do some research on collinearity to come up with another solution for this problem. I was able to remember one thing about points and lines that anybody who went through high school algebra should have drilled in their brains: y = mx + b. The important part is the b, or the slope.

Before I get too far ahead let’s break down the problem’s desires and see what it is we need to vanquish this challenge.

This challenge can be found here.

Understanding the problem

The outcome is in the title of this solution: check if it is a straight line. Sometimes you can guess what data type you will be returning by the title of a challenge. If you guessed a boolean value… you win 1 million imaginary congratulatory pats on the back!!! Nice.

For clarity, I will quote the challenge’s definition:

“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.”

Our input is an array of arrays. Each array in the given array is a pair of x,y coordinates. All we have to do is see if all the coordinates lay on the same line.

Going back to what I was saying about y=mx+b, we can determine if coordinates are on the same line if they have the same slope, or the b in y=mx+b.

How can we get the slope between two coordinates? Easy. Subtract the next coordinate from the previous coordinate. Do this: (y2 -y) / (x2 -x) = slope.

One important thing to realize is that the first two coordinates given will always be straight line. Because you can make a line with any two points in space. That said, if our coordinates array is only 2 in length, we automatically know that it is a line. Return true.

If our coordinates array is longer than 2 then we need to store the initial slope of the first two coordinates and check that slope against the remaining coordinate’s slopes (the difference between the current coordinate and the one before it. Or the next coordinate and the current coordinate. Depending on how you want to implement it).

Here’s some pseudo-code for the process.

Pseudo-code:

1. If only 2 coords, return true (always a line)
2. The slope of the line can be determined from the first two points given. Set a variable ‘slope’ which is the difference of [ coords[1][1] -coords[0][1], coords[1][0] -coords[0][0] ]
3. Loop through remaining coords and check if the difference between the current coord and the previous is the same as the slope
4. If it’s not, return false
5. Default to return true

And now for the real thing.

The code:

O(n) Time Complexity / O(1) Space Complexity

If you look closely at our for loop you will notice we are starting index i at 2. This is because we have already processed the first two coordinates by setting the slope variable to the difference of (y2-y)/(x2-x).

That does the job! But is there another way we could have done this? There sure is.

Another solution:

I was curious about finding collinearity between two coordinates, so I did some research and found this nifty webpage that has a few different approaches for resolving collinearity.

See: https://mathworld.wolfram.com/Collinear.html

A simple one that stood out to me is solving for the area of a Triangle. The web page states:

“A slightly more tractable condition is obtained by noting that the area of a triangle determined by three points will be zero iff they are collinear”

Basically if we use this formula: x1(y2 -y3) + x2(y3 -y1) + x3(y1 -y2) and the outcome is 0 then the coordinates are collinear.

Now we are dealing with 3 coordinates at once so we will have to adjust our code to manage this.

Pseudo-code:

1. If only 2 coords, return true (always a line)
2. Collinearity can be determined by checking for the area of Triangle with 3 coordinates, if you get 0 then they are collinear. Otherwise, return false
3. Loop through coords and check for collinearity based on the explanation above
4. Default to return true

I heavily simplified this pseudo-code, but the gist is there. We have our formula we just need to implement it inside of our loop.

The code:

O(n) Time Complexity / O(1) Space Complexity

This time our for loop is starting i at index 1. This is so we can grab the previous index, the current index, and the next index in each loop. You may also notice that our index i will only loop while i<coords.length -1. This is important because if we allowed our index i to become the last index in coords then our code would break at const [x3, y3] = coords[i + 1].

Our if statement is the formula for the area of a triangle given 3 coordinates translated into JavaScript terms. If the outcome is not 0, then we return false (this tells us the coordinates are not collinear).

One last thing! If the syntax in my variable definitions look weird then you have not read up on object destructuring in JavaScript yet. You can do so here.

If you have another solution or any advice, let me know. Take care!