Valid Boomerang: Cross Product for Collinearity

You are given an array points where points[i] = [xi, yi] represents a point on the X-Y plane. Return true if these points form a boomerang. A boomerang is a set of three points that are all distinct and not in a straight line.

This is LeetCode 1037: Valid Boomerang, and it is a great introduction to using the cross product for geometry problems on integer coordinates.

Why this problem matters

At first glance, checking whether three points are collinear might seem like a slope comparison problem. You could compute the slope between each pair and see if they match. But slopes involve division, and division introduces floating-point errors and the annoying special case of vertical lines (division by zero).

The cross product sidesteps all of that. It uses only multiplication and subtraction, works entirely in integers, and handles every orientation of points without any special cases. Once you learn this technique here, you can apply it to more advanced geometry problems like finding the largest triangle area, checking convex hulls, and counting collinear points.

The key insight

Three points are collinear (lie on the same line) if and only if the cross product of the two vectors formed by those points equals zero.

Given three points (x1, y1), (x2, y2), and (x3, y3), you form two vectors from the first point:

• Vector A: (x2 - x1, y2 - y1)
• Vector B: (x3 - x1, y3 - y1)

The 2D cross product of A and B is:

cross = (x2 - x1) * (y3 - y1) - (y2 - y1) * (x3 - x1)

If cross == 0, the vectors are parallel, meaning the three points are collinear. If cross != 0, the points form a triangle, which is a valid boomerang.

The problem guarantees distinct points are possible, but two points could still be the same. If any two points are identical, the cross product will be zero, correctly returning false.

The solution

def is_boomerang(points: list[list[int]]) -> bool:
    x1, y1 = points[0]
    x2, y2 = points[1]
    x3, y3 = points[2]
    return (x2 - x1) * (y3 - y1) - (y2 - y1) * (x3 - x1) != 0

That is the entire solution. Let's break it down.

We unpack the three points into their x and y coordinates. Then we compute the cross product of the vectors from point 1 to point 2 and from point 1 to point 3. If the cross product is non-zero, the points are not collinear, so they form a valid boomerang. If it is zero, the points are on the same line (or two of them are identical), and we return false.

There is no need for sorting, no need for floating-point arithmetic, and no edge case handling for vertical or horizontal lines. The cross product formula covers everything in one expression.

Visual walkthrough

Let's trace through the cross product computation step by step for both a valid boomerang and a collinear case.

Notice how the entire decision comes down to a single arithmetic expression. When the cross product is non-zero (like -3 in the first example), the three points form a triangle. When it is zero (like in the collinear example), they all sit on the same line.

Complexity analysis

Time is O(1). You perform a fixed number of arithmetic operations regardless of input size. There are exactly three points, and you do a constant amount of work with them.

Space is O(1). You store only a few integer variables for the coordinates and the cross product result. No additional data structures are needed.

The building blocks

1. Cross product for collinearity

The pattern of using the 2D cross product to determine whether three points are collinear:

def are_collinear(p1, p2, p3):
    x1, y1 = p1
    x2, y2 = p2
    x3, y3 = p3
    return (x2 - x1) * (y3 - y1) - (y2 - y1) * (x3 - x1) == 0

This pattern appears whenever you need to check whether points lie on the same line. You will use it in "Max Points on a Line" (grouping points by collinearity), "Largest Triangle Area" (computing area via cross product), and convex hull algorithms. The formula is always the same: form two vectors from a shared point and compute their cross product.

2. Geometry on integer coordinates

The pattern of avoiding floating-point arithmetic by using multiplication-based formulas on integer inputs:

cross = (x2 - x1) * (y3 - y1) - (y2 - y1) * (x3 - x1)

When your inputs are integers, you can often avoid division entirely. Slopes become cross products. Distance comparisons use squared distances. Area calculations use the shoelace formula (which is based on cross products). Keeping everything in integers eliminates floating-point precision issues and makes equality checks reliable.

Edge cases

Before submitting, think through these scenarios:

• Two identical points: if points[0] == points[1], both vectors share the same origin and destination, making the cross product zero. Correctly returns false.
• All three points identical: cross product is zero. Correctly returns false.
• Vertical alignment: points like (1,1), (1,2), (1,3) are collinear vertically. The cross product is 0*2 - 1*0 = 0. No division-by-zero issues.
• Horizontal alignment: points like (1,1), (2,1), (3,1). Cross product is 1*0 - 0*2 = 0. Correctly identified as collinear.
• Large coordinates: since the problem uses integer coordinates, the cross product stays within integer range. No overflow concerns with typical constraint sizes.
• Negative coordinates: the formula works identically for negative values. No special handling needed.

From understanding to recall

The cross product collinearity check is one of those formulas that is easy to look up but surprisingly easy to get wrong under pressure. Which coordinate gets subtracted from which? Is it dx1 * dy2 or dx1 * dx2? Do you check == 0 or != 0 for the boomerang case?

These are not conceptual gaps. They are recall gaps. You understand the math, but your fingers hesitate when it is time to write the formula. Spaced repetition fixes this. You practice writing the cross product formula from memory, first daily, then every few days, then weekly. After a handful of repetitions, the pattern is automatic. You see "three points, check collinear" and the formula flows out without a pause.

Related posts

• Max Points on a Line - Uses the same collinearity check for grouping points
• Largest Triangle Area - Another geometry problem with 3 points using the cross product
• Rectangle Area - Geometric calculations on coordinate points

CodeBricks breaks Valid Boomerang into its cross product and integer geometry building blocks, then drills them independently with spaced repetition. You type the formula from scratch until it is automatic. When a geometry question shows up in your interview, you do not fumble with slopes and edge cases. You just write the cross product and move on.