Problem Explanation

Given an array of points in the form of [x,y] coordinates, we are required to determine whether these points form a straight line.

The fundamental approach to this would be to leveragethe geometric property which states that the slope between any two points in a line is constant. Mathematically, the slope between two points (x1, y1) and (x2, y2) is (y2 - y1) / (x2 - x1). We calculate the slope between the first two points and then for each subsequent point, check if the slope between the current point and the first point is the same as the initial slope.

Example

Let's walkthrough an example to illustrate how the algorithm works.

Consider the case where the input coordinates are [[1,2],[2,3],[3,4],[4,5],[5,6],[6,7]], which forms a straight line. Here are the steps of our algorithm:

1. Compare the slope between the first two points, which is (3 - 2) / (2 - 1) = 1.

2. Iterate through each subsequent point comparing the slope between the current point and the first point with the initial slope (1). For example, the next point is [3,4], and the slope between this point and the first point is (4 - 2) / (3 - 1) = 1 which equals to our initial slope.

3. If we find a point where the slope does not match, return false. Otherwise, return true.

Solution

C++ Solution

1
2cpp
3class Solution {
4public:
5    bool checkStraightLine(vector<vector<int>>& coordinates) {
6        
7        int dx = coordinates[1][0] - coordinates[0][0];
8        int dy = coordinates[1][1] - coordinates[0][1];
9        
10        for (int i = 2; i < coordinates.size(); ++i) {
11            int x = coordinates[i][0];
12            int y = coordinates[i][1];
13            if (dx*(y-coordinates[0][1]) != dy*(x-coordinates[0][0]))
14                return false;
15        }
16        return true;
17    }
18};

Python Solution

1
2python
3class Solution:
4    def checkStraightLine(self, coordinates: List[List[int]]) -> bool:
5        x0, y0 = coordinates[0]
6        x1, y1 = coordinates[1]
7        dx = x1 - x0
8        dy = y1 - y0
9        
10        for i in range(2, len(coordinates)):
11            x, y = coordinates[i]
12            if dx*(y - y0) != dy*(x - x0):
13                return False
14    }

Java Solution

1
2java
3class Solution {
4    public boolean checkStraightLine(int[][] coordinates) {
5        int dx = coordinates[1][0] - coordinates[0][0];
6        int dy = coordinates[1][1] - coordinates[0][1];
7        
8        for(int i=2; i<coordinates.length; i++){
9            if(dx*(coordinates[i][1] - coordinates[0][1]) != dy*(coordinates[i][0] - coordinates[0][0])){
10                return false;
11            }
12        }
13        return true;
14    }
15}

JavaScript Solution

1
2js
3class Solution {
4  checkStraightLine(coordinates) {
5        let dx = coordinates[1][0] - coordinates[0][0];
6        let dy = coordinates[1][1] - coordinates[0][1];
7        
8        for(let i=2; i<coordinates.length; i++){
9            if(dx*(coordinates[i][1] - coordinates[0][1]) != dy*(coordinates[i][0] - coordinates[0][0])){
10                return false;
11            }
12        }
13        return true;
14    }
15}

C# Solution

1
2csharp
3public class Solution {
4    public bool CheckStraightLine(int[][] coordinates) {
5        int dx = coordinates[1][0] - coordinates[0][0];
6        int dy = coordinates[1][1] - coordinates[0][1];
7        
8        for(int i=2; i<coordinates.Length; i++){
9            if(dx*(coordinates[i][1] - coordinates[0][1]) != dy*(coordinates[i][0] - coordinates[0][0])){
10                return false;
11            }
12        }
13        return true;
14    }
15}

Conclusion

The central idea here is to employ the geometric principle that the slope between any two points on a line remains constant. Hence, all it takes is the calculation of the slope between the initial two points and then iterating through the remaining points to check if this property is preserved.

The solutions for C++, Python, Java, JavaScript, and C# provided here are very efficient, both in terms of time and space complexity. They all run in O(n) time, where n is the number of points provided in the input, since we are merely conducting a single pass through the array. And, no additional space is used, meaning all solutions have a space complexity of O(1).

This problem can serve as a good illustration of how understanding and applying simple mathematical concepts make problem-solving in computer science relatively straightforward. Practicing problems like this will surely build your mathematical intuition and problem-solving ability!