Check If It Is a Straight Line: Cross Multiplication Pattern

You are given an array of coordinates where coordinates[i] = [x, y] represents a point on the X-Y plane. Return true if the points form a straight line, and false otherwise.

This is LeetCode 1232: Check If It Is a Straight Line, and it is one of the best problems for learning how to check collinearity without running into division-by-zero errors. The cross multiplication technique it teaches shows up in geometry problems across all difficulty levels.

Why this problem matters

Checking whether points are collinear is a fundamental geometry operation. The naive approach computes slopes and compares them, but slopes involve division, and division by zero happens whenever two points share the same x-coordinate. That edge case is easy to forget under pressure.

Cross multiplication eliminates the problem entirely. Instead of comparing dy1/dx1 == dy2/dx2, you compare dy1 * dx2 == dy2 * dx1. No division, no special cases, no floating point errors. Once you internalize this trick, you can apply it to problems like Valid Boomerang (LeetCode 1037), Max Points on a Line (LeetCode 149), and any problem that checks whether points are collinear.

The key insight

Take the first two points to define a reference direction: dx = x1 - x0 and dy = y1 - y0. For every other point (xi, yi), the point lies on the same line if and only if:

dy * (xi - x0) == dx * (yi - y0)

This is the cross multiplication form of the slope equality check. If the slope from P0 to P1 equals the slope from P0 to Pi, then (y1 - y0) / (x1 - x0) == (yi - y0) / (xi - x0). Cross-multiplying both sides gives the equation above, and it works even when dx or (xi - x0) is zero.

The algorithm:

1. Compute dx = x1 - x0 and dy = y1 - y0 from the first two points.
2. For each subsequent point (xi, yi), check if dy * (xi - x0) == dx * (yi - y0).
3. If any point fails the check, return false. If all pass, return true.

The solution

def check_straight_line(coordinates: list[list[int]]) -> bool:
    x0, y0 = coordinates[0]
    x1, y1 = coordinates[1]
    dx = x1 - x0
    dy = y1 - y0

    for i in range(2, len(coordinates)):
        xi, yi = coordinates[i]
        if dy * (xi - x0) != dx * (yi - y0):
            return False

    return True

The first two lines unpack the reference points and compute the direction vector (dx, dy). The loop then checks every remaining point against this reference.

The core comparison dy * (xi - x0) != dx * (yi - y0) is the cross multiplication check. If the cross product of the two direction vectors is non-zero, the point does not lie on the line, and we return false immediately.

If the loop completes without finding a deviation, all points are collinear and we return true.

Visual walkthrough

Let's trace through coordinates = [[1,2],[2,3],[3,4],[4,5],[5,6],[6,7]] step by step. Watch how the cross multiplication check compares each point against the reference direction defined by the first two points.

Every point produces matching values on both sides of the equation. That means all six points are collinear, and the function returns true. In the contrast example, point (3,4) produces 2 on one side and 3 on the other, so the function returns false immediately without checking the remaining points.

Complexity analysis

Time is O(n) where n is the number of coordinates. You compute the reference direction in O(1), then check each of the remaining n-2 points with a single multiplication and comparison. The total work is linear.

Space is O(1). You only store the reference direction (dx, dy) and a loop variable. No extra data structures are needed.

The building blocks

1. Cross multiplication for ratio comparison

The pattern of avoiding division by cross-multiplying both sides of an equality:

dx = x1 - x0
dy = y1 - y0
if dy * (xi - x0) != dx * (yi - y0):
    return False

This replaces the fragile slope comparison (y1 - y0) / (x1 - x0) == (yi - y0) / (xi - x0) with a multiplication that never divides by zero. You will reuse this exact pattern in Valid Boomerang (three points), Max Points on a Line (counting collinear groups), and any geometry problem that involves slope comparisons.

2. Early exit on first failure

The pattern of returning false as soon as one element violates the condition:

for i in range(2, len(coordinates)):
    xi, yi = coordinates[i]
    if dy * (xi - x0) != dx * (yi - y0):
        return False
return True

This is a general verification pattern. You assume the answer is true and scan for a counterexample. The moment you find one, you exit. This saves time in the average case and keeps the code clean. You see this structure in problems like Valid Palindrome, Valid Anagram, and any "check if all elements satisfy a condition" problem.

Edge cases

Before submitting, think through these scenarios:

• Only two points: any two points always form a line. The loop body never executes, so the function returns true.
• Vertical line: all points share the same x-coordinate. dx = 0, but cross multiplication handles this correctly because 0 * (xi - x0) is always 0, and dx * (yi - y0) is also 0 for any yi.
• Horizontal line: all points share the same y-coordinate. dy = 0, and the check becomes 0 == 0 for every point on the line.
• Duplicate points: if multiple points are the same as P0, the check becomes dy * 0 == dx * 0, which is 0 == 0. Duplicates always pass.
• Large coordinates: the multiplication dy * (xi - x0) can produce large values. In Python, integers have arbitrary precision, so overflow is not a concern. In languages like Java or C++, you may need to cast to long.

From understanding to recall

You have seen how cross multiplication turns a collinearity check into a single-pass linear scan with no division and no edge cases. The logic is clean: compute a reference direction, then verify every point against it.

The detail that trips people up is remembering which terms go where. Is it dy * (xi - x0) or dx * (xi - x0)? Do you subtract x0 or x1? These are not conceptual gaps. They are recall gaps, and they cost time under pressure.

Spaced repetition is how you close them. You practice writing the cross multiplication check from memory at increasing intervals. After a few rounds, the formula is automatic. You see "are these points collinear" in a problem, and the dy * (xi - x0) == dx * (yi - y0) pattern flows out without hesitation.

Related posts

• Valid Boomerang - The three-point collinearity check using the same cross product technique
• Max Points on a Line - Counting the maximum number of collinear points with hash maps and slope grouping
• Projection Area of 3D Shapes - Another geometry problem that builds spatial reasoning from simple building blocks

CodeBricks breaks Check If It Is a Straight Line into its cross multiplication and early-exit building blocks, then drills them independently with spaced repetition. You type each piece from scratch until the pattern is automatic. When a geometry problem shows up in your interview, you do not think about it. You just write it.