How do you solve Check If It Is a Straight Line on LeetCode?

Check If It Is a Straight Line (LeetCode #1232) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(n) time complexity and O(1) space complexity. Key insight: Two points define a line.

What is the time complexity of Check If It Is a Straight Line?

The optimal solution for Check If It Is a Straight Line runs in O(n) time and uses O(1) space. This complexity is linear because we only traverse the list of coordinates once, checking the condition for each point.

What is the brute force solution for Check If It Is a Straight Line?

The brute force approach for Check If It Is a Straight Line is Brute Force, with O(n²) time complexity and O(1) space complexity. To check if all points lie on a straight line, we can compare the slope between each point and the first two points. If all slopes are equal, the points are collinear. The optimal Optimal Solution approach improves this to O(n).

What algorithm or data structure is used to solve Check If It Is a Straight Line?

Check If It Is a Straight Line uses the following concepts: Array, Math, Geometry. The recommended patterns to study are: Geometry, Mathematical Properties.

What are the interview tips for Check If It Is a Straight Line?

Always check edge cases, like the minimum number of points. Explain your thought process clearly as you code. Use simple mathematical properties to simplify your checks.

What are common mistakes when solving Check If It Is a Straight Line?

Not handling the case of only two points correctly. Confusing slope calculations with division, leading to potential division by zero.

#1232

Check If It Is a Straight Line

Easy

ArrayMathGeometryGeometryMathematical Properties

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n²)	O(n)
Space	O(1)	O(1)

💡

Intuition

Time O(n)Space O(1)

Instead of checking slopes for every point, we can use the concept of cross products to determine if points are collinear, which is more efficient.

⚙️

Algorithm

3 steps

1Step 1: If there are only 2 points, return true.
2Step 2: Calculate the differences dx1 = x2 - x1 and dy1 = y2 - y1 for the first two points.
3Step 3: For each subsequent point, calculate dx2 = x - x1 and dy2 = y - y1, and check if dx1 * dy2 == dy1 * dx2.

solution.py12 lines

1# Full working Python code
2
3def checkStraightLine(coordinates):
4    if len(coordinates) == 2:
5        return True
6    (x1, y1), (x2, y2) = coordinates[0], coordinates[1]
7    dx1, dy1 = x2 - x1, y2 - y1
8    for x, y in coordinates[2:]:
9        dx2, dy2 = x - x1, y - y1
10        if dx1 * dy2 != dy1 * dx2:
11            return False
12    return True

ℹ

Complexity note: This complexity is linear because we only traverse the list of coordinates once, checking the condition for each point.

1Two points define a line.
2Collinearity can be checked using cross products.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.