1232. Check If It Is a Straight Line
Problem Description
The problem presents us with an array called coordinates
. Each element within this array is itself an array that represents a point in the form [x, y]
āwhere x
is the x-coordinate and y
is the y-coordinate of a point on the XY plane. The task is to determine if all these points lie on a single straight line or not.
Intuition
To check if points lie on the same straight line, we need to ensure that the slope between any two points is the same across all points. The slope is a measure of how steep a line is. If pairs of points have different slopes, the points do not lie on a single straight line.
To calculate the slope between two points (x1, y1)
and (x2, y2)
, we use the formula slope = (y2 - y1) / (x2 - x1)
. If the slope is consistent between consecutive points, then all the points are on the same line.
In our solution, we take the first two points from coordinates
to calculate a reference slope. For computational efficiency and to avoid the potential division by zero error, we check the equality of slopes using a cross-multiplication method. Specifically, instead of directly computing (y2 - y1) / (x2 - x1) == (y - y1) / (x - x1)
, we check if (x - x1) * (y2 - y1) == (y - y1) * (x2 - x1)
for subsequent points (x, y)
.
If the equality holds for all pairs of points in the coordinates array, the function returns True
, which means all points lie on a single straight line. If any pair of points fails the equality test, the function returns False
, and we know that not all points are on the same line.
The intuition behind this approach is that we're using the properties of slopes in a way that's computationally efficient and avoids possible arithmetic errors when dealing with real numbers.
Learn more about Math patterns.
Solution Approach
The algorithm follows a straightforward approach by checking if the slope between any two points is the same across all points. No additional data structures or complex patterns are necessary. The algorithm involves simple arithmetic operations and a for loop. Here's a step-by-step implementation break down:
-
The algorithm starts by storing the x and y coordinates of the first two points from the
coordinates
array inx1, y1
andx2, y2
. These two points are used to find the reference slope for the line. -
The algorithm then iterates over the remaining points in
coordinates
, starting from the third point, using afor x, y in coordinates[2:]:
loop. -
Inside the loop, for each point
(x, y)
, the algorithm checks if the cross-product of the differences in coordinates between point(x, y)
and the first point(x1, y1)
equals the cross-product of the differences between the second point(x2, y2)
and the first point.The check is made using the following condition:
if (x - x1) * (y2 - y1) != (y - y1) * (x2 - x1): return False
This expression is derived from the slope equality
slope1 = slope2
. Instead of dividing the differences, which can cause a division by zero, it multiplies the opposite sides and compares them for equality. -
If the check fails for any point, the function immediately returns
False
, indicating that the points do not all lie on the same straight line. -
If the loop completes without encountering any point that fails the slope check, the function returns
True
, signaling that all points do indeed lie on a straight line.
The time complexity of this algorithm is O(n), where n is the number of points, since we have to check the condition for each point once. The space complexity is O(1) since we are using a fixed amount of additional space regardless of the number of points.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's walk through a small example to illustrate the solution approach:
Suppose coordinates = [[1, 2], [2, 3], [3, 4]]
. We are looking to confirm whether these points fall on a single straight line.
-
Based on our algorithm, we first take the coordinates of the first two points to calculate the reference slope. So from our
coordinates
, we havex1, y1 = 1, 2
andx2, y2 = 2, 3
. -
Next, the algorithm will iterate over the remaining points in
coordinates
. Since we only have three points in this example, it will iterate over just one point:[3, 4]
. -
Now, the algorithm will check if the cross-product of differences with the new point
[3, 4]
, denoted as(x, y)
, and the first point(x1, y1)
equals the cross-product of the differences between the second point(x2, y2)
and the first point. This equation looks like:if (3 - 1) * (3 - 2) != (4 - 2) * (2 - 1):
Simplifying the expressions on each side of the inequality gives:
if 2 * 1 != 2 * 1:
In this case, both sides are equal, meaning that the slope between point
[1, 2]
and point[3, 4]
is the same as the slope between point[1, 2]
and point[2, 3]
. -
Since there are no more points to check, and the equality held true for the third point, the algorithm would return
True
. -
This confirms that all the given points in the example line
[1, 2], [2, 3], [3, 4]
are on the same straight line.
If we had a point that did not satisfy the slope equality, for example [4, 5]
replaced by [4, 6]
, the algorithm would compare:
if (4 - 1) * (3 - 2) != (6 - 2) * (2 - 1):
which simplifies to:
if 3 != 4:
This inequality is true, indicating that the point [4, 6]
does not lie on the same straight line as the others, so the algorithm would return False
.
Solution Implementation
1from typing import List
2
3class Solution:
4 def checkStraightLine(self, coordinates: List[List[int]]) -> bool:
5 # Extract the first 2 points
6 first_point = coordinates[0]
7 second_point = coordinates[1]
8
9 # Coordinates of the first point
10 x1, y1 = first_point
11
12 # Coordinates of the second point
13 x2, y2 = second_point
14
15 # Check if the subsequent points are in a straight line
16 for point in coordinates[2:]:
17 x, y = point
18
19 # Use the cross product to determine if three points are on the same line:
20 # (x - x1)/(x2 - x1) should be equal to (y - y1)/(y2 - y1)
21 # Cross-multiplying to avoid division (to handle the case when x2 - x1 is 0) we get:
22 # (x - x1) * (y2 - y1) should be equal to (y - y1) * (x2 - x1)
23 # If they are not equal for any point, the points do not form a straight line
24 if (x - x1) * (y2 - y1) != (y - y1) * (x2 - x1):
25 return False
26
27 # If the loop completes without returning False, all points are in a straight line
28 return True
29
1class Solution {
2
3 /**
4 * Checks if all the given points lie on a straight line.
5 *
6 * @param coordinates Array of point coordinates on a 2D plane.
7 * @return true if all points lie on a single straight line, false otherwise.
8 */
9 public boolean checkStraightLine(int[][] coordinates) {
10 // Coordinates of the first point
11 int x1 = coordinates[0][0];
12 int y1 = coordinates[0][1];
13
14 // Coordinates of the second point
15 int x2 = coordinates[1][0];
16 int y2 = coordinates[1][1];
17
18 // Loop over the rest of the points starting from the third one
19 for (int i = 2; i < coordinates.length; i++) {
20 // Coordinates of the current point
21 int currentX = coordinates[i][0];
22 int currentY = coordinates[i][1];
23
24 // Check if the current point lies on the line formed by the first two points
25 // This is done by using the cross product which should be zero for collinear points
26 int deltaX1 = currentX - x1;
27 int deltaY1 = y2 - y1;
28 int deltaY2 = currentY - y1;
29 int deltaX2 = x2 - x1;
30
31 // If current point does not satisfy the line equation then return false
32 if (deltaX1 * deltaY1 != deltaY2 * deltaX2) {
33 return false;
34 }
35 }
36
37 // If all the points satisfy the line equation then return true
38 return true;
39 }
40}
41
1#include<vector> // Needed to use std::vector
2using std::vector;
3
4class Solution {
5public:
6 // Function to check if all points lie on a straight line.
7 bool checkStraightLine(vector<vector<int>>& coordinates) {
8 // Extract the first point (x1,y1)
9 int x1 = coordinates[0][0], y1 = coordinates[0][1];
10 // Extract the second point (x2,y2)
11 int x2 = coordinates[1][0], y2 = coordinates[1][1];
12
13 // Loop through all the remaining points
14 for (int i = 2; i < coordinates.size(); ++i) {
15 // Extract the current point (x,y)
16 int x = coordinates[i][0], y = coordinates[i][1];
17
18 // Check if the cross product of the vectors is zero
19 // This is a vector algebra way of checking colinearity:
20 // (x-x1)/(x2-x1) should be equal to (y-y1)/(y2-y1) for all points on the line
21 // By cross-multiplying to avoid division (and potential division by zero),
22 // we get (x-x1)*(y2-y1) == (y-y1)*(x2-x1)
23 if ((x - x1) * (y2 - y1) != (y - y1) * (x2 - x1)) {
24 return false; // The current point doesn't lie on the straight line defined by the first two points
25 }
26 }
27 // All points lie on the same straight line
28 return true;
29 }
30};
31
1// Necessary import statement when working with arrays in TypeScript
2import { Vector } from 'prelude-ts';
3
4// Function to check if all points lie on a straight line.
5function checkStraightLine(coordinates: number[][]): boolean {
6 // Extract the first point (x1, y1)
7 const x1 = coordinates[0][0];
8 const y1 = coordinates[0][1];
9
10 // Extract the second point (x2, y2)
11 const x2 = coordinates[1][0];
12 const y2 = coordinates[1][1];
13
14 // Loop through all the remaining points
15 for (let i = 2; i < coordinates.length; i++) {
16 // Extract the current point (x, y)
17 const x = coordinates[i][0];
18 const y = coordinates[i][1];
19
20 // Check if the cross product of the vectors is zero
21 // This is a vector algebra way of checking collinearity:
22 // (x-x1)/(x2-x1) should be equal to (y-y1)/(y2-y1) for all points on the line
23 // By cross-multiplying to avoid division (and potential division by zero),
24 // we get (x-x1) * (y2-y1) == (y-y1) * (x2-x1)
25 if ((x - x1) * (y2 - y1) !== (y - y1) * (x2 - x1)) {
26 return false; // The current point doesn't lie on the straight line defined by the first two points
27 }
28 }
29
30 // All points lie on the same straight line
31 return true;
32}
33
Time and Space Complexity
Time Complexity
The time complexity of the function checkStraightLine
is O(n)
, where n
is the number of coordinate points in the input list coordinates
. This is because the function uses a single loop that iterates through the coordinates starting from the third element, and for each iteration, it performs a constant number of mathematical operations to check if the points lie on the same line. These operations do not depend on the size of the input other than the fact that they iterate once for each element beyond the first two.
Space Complexity
The space complexity of the function is O(1)
. The function uses a fixed amount of extra space to store the variables x1
, y1
, x2
, y2
, x
, and y
. The amount of space used does not scale with the size of the input list, meaning that the space usage is constant.
Learn more about how to find time and space complexity quickly using problem constraints.
How many times is a tree node visited in a depth first search?
Recommended Readings
Math for Technical Interviews How much math do I need to know for technical interviews The short answer is about high school level math Computer science is often associated with math and some universities even place their computer science department under the math faculty However the reality is that you
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Want a Structured Path to Master System Design Too? Donāt Miss This!