LeetCode 1232 - Check If It Is a Straight Line

LeetCode Problem 1232

Difficulty: 🟢 Easy
Topics: Array, Math, Geometry

Solution

Problem Understanding

The problem asks us to determine whether a given set of points in a 2D Cartesian plane all lie on a single straight line. The input is a list of integer coordinates, where each coordinate [x, y] represents a point. The expected output is a boolean: true if all the points lie on a straight line, and false otherwise.

The constraints give us key information. First, there are at least two points (2 <= coordinates.length <= 1000), so we always have at least a line segment to check. Each coordinate is bounded (-10^4 <= x, y <= 10^4) and no points are duplicated, which simplifies slope calculations because we do not need to handle identical points causing division by zero in slope calculations.

Important edge cases include vertical lines, where the slope would be undefined if calculated as (y2 - y1) / (x2 - x1), and horizontal lines, where the slope is zero. The problem guarantees no duplicate points, so we do not need to handle multiple points at the same coordinates.

In short, we are asked to check the collinearity of a list of points.

Approaches

The brute-force approach is to calculate the slope between the first point and every other point. If all slopes are equal, the points lie on a straight line. While this works, it requires division, which can lead to floating-point precision issues, especially when working with integers.

A better, optimal approach avoids division by using the cross product of vectors. For three points (x0, y0), (x1, y1), (x2, y2), they are collinear if the slope between the first two points equals the slope between the first and third point. Using the cross product formula:

(y2 - y0) * (x1 - x0) == (y1 - y0) * (x2 - x0)

This avoids floating-point operations and handles vertical lines naturally, providing a robust integer-only solution.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n)	O(1)	Calculate slope with division, prone to precision issues
Optimal	O(n)	O(1)	Use cross-product for slope comparison, handles vertical lines safely

Algorithm Walkthrough

1. Take the first two points, p0 and p1, to define the line. Calculate the differences dx = x1 - x0 and dy = y1 - y0.
2. Iterate over the remaining points from the third point onward.
3. For each point (xi, yi), check if it satisfies the collinearity condition using the cross product: (yi - y0) * dx == (xi - x0) * dy.
4. If any point fails this check, return false immediately since the points are not collinear.
5. If all points satisfy the condition, return true.

Why it works: The cross-product condition ensures that the slope between the initial line segment (p0, p1) and any other point is the same. Collinearity is preserved if this equation holds for all points.

Python Solution

from typing import List

class Solution:
    def checkStraightLine(self, coordinates: List[List[int]]) -> bool:
        x0, y0 = coordinates[0]
        x1, y1 = coordinates[1]
        dx = x1 - x0
        dy = y1 - y0
        
        for x, y in coordinates[2:]:
            if (y - y0) * dx != (x - x0) * dy:
                return False
        return True

In this implementation, we first extract the first two points and compute the differences dx and dy. We then iterate through all remaining points and check the cross-product condition to verify collinearity. If any point violates the condition, we return false. Otherwise, after the loop, all points are collinear, and we return true.

Go Solution

func checkStraightLine(coordinates [][]int) bool {
    x0, y0 := coordinates[0][0], coordinates[0][1]
    x1, y1 := coordinates[1][0], coordinates[1][1]
    dx := x1 - x0
    dy := y1 - y0

    for i := 2; i < len(coordinates); i++ {
        xi, yi := coordinates[i][0], coordinates[i][1]
        if (yi - y0) * dx != (xi - x0) * dy {
            return false
        }
    }
    return true
}

The Go implementation mirrors the Python solution. We extract the first two points, compute the differences dx and dy, and iterate through remaining points to verify the cross-product condition. Go handles integer arithmetic safely, so there is no need for floating-point checks.

Worked Examples

Example 1: coordinates = [[1,2],[2,3],[3,4],[4,5],[5,6],[6,7]]

Iteration	x	y	(y-y0)*dx	(x-x0)*dy	Collinear?
2	3	4	(4-2)*1 = 2	(3-1)*1 = 2	True
3	4	5	3	3	True
4	5	6	4	4	True
5	6	7	5	5	True

All points satisfy the condition, so the output is true.

Example 2: coordinates = [[1,1],[2,2],[3,4],[4,5],[5,6],[7,7]]

Iteration	x	y	(y-y0)*dx	(x-x0)*dy	Collinear?
2	3	4	(4-1)*1 = 3	(3-1)*1 = 2	False

The third point fails the condition, so the output is false.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Each point is checked exactly once in a loop, so linear in the number of points
Space	O(1)	Only a few variables are stored; no extra data structures are used

The linear time complexity is optimal because every point must be examined to ensure collinearity. The constant space complexity is achieved by only storing the first two points' differences and iterating over the array in place.

Test Cases

# Provided examples
assert Solution().checkStraightLine([[1,2],[2,3],[3,4],[4,5],[5,6],[6,7]]) == True  # All points in line
assert Solution().checkStraightLine([[1,1],[2,2],[3,4],[4,5],[5,6],[7,7]]) == False  # One point off

# Minimum input size
assert Solution().checkStraightLine([[0,0],[1,1]]) == True  # Two points always form a line

# Horizontal line
assert Solution().checkStraightLine([[0,5],[1,5],[2,5]]) == True

# Vertical line
assert Solution().checkStraightLine([[3,0],[3,1],[3,2]]) == True

# Negative coordinates
assert Solution().checkStraightLine([[-1,-1],[0,0],[1,1],[2,2]]) == True

# Large numbers
assert Solution().checkStraightLine([[10000,10000],[20000,20000],[30000,30000]]) == True

Test	Why
All points in line	Confirms basic functionality
One point off	Detects failure case
Two points only	Ensures minimum input handled
Horizontal line	Checks zero slope
Vertical line	Checks undefined slope
Negative coordinates	Verifies handling of negative values
Large numbers	Confirms no integer overflow issues

Edge Cases

One important edge case is a vertical line, where dx = 0. A naive slope-based approach would divide by zero, but the cross-product method handles this safely by avoiding division entirely.

A second edge case is a horizontal line, where dy = 0. Here, all y-coordinates must be equal. The cross-product condition (y-y0)*dx == (x-x0)*dy naturally reduces to (0 == 0), correctly identifying horizontal lines.

A third edge case is using the minimum number of points, two. Any two points always define a straight line, so the algorithm should return true immediately. The implementation handles this by iterating starting from the third point, so two points do not enter the loop.