Given an array points where points[i] = [xi, yi] represents a point on the X-Y plane, return true if these points are a boomerang.
A boomerang is a set of three points that are all distinct and not in a straight line.
Example 1:
Input: points = [[1,1],[2,3],[3,2]] Output: true
Example 2:
Input: points = [[1,1],[2,2],[3,3]] Output: false
Constraints:
points.length == 3points[i].length == 20 <= xi, yi <= 100Problem Overview: You are given three points on a 2D plane. A boomerang is valid only if the points are all distinct and they do not lie on the same straight line. The task is to determine whether these three coordinates form a non‑collinear triangle.
The core observation: three points form a straight line if their slopes match or if the area of the triangle formed by them equals zero. Both approaches rely on basic geometry and simple math operations on coordinates stored in an array.
Approach 1: Using Slope to Determine Collinearity (Time: O(1), Space: O(1))
Two line segments share the same slope when three points are collinear. Compute the slope between point A→B and A→C and compare them. Instead of dividing (which risks floating‑point errors or division by zero), use cross multiplication: (y2 - y1) * (x3 - x1) == (y3 - y1) * (x2 - x1). If this equality holds, the slopes are identical and the points lie on the same line. Otherwise, they form a valid boomerang.
This method relies purely on integer arithmetic, which avoids precision problems and keeps the implementation clean. Since the input always contains exactly three points, you perform only a constant number of operations. That makes the runtime O(1) and space O(1). This is usually the most straightforward way to solve the problem.
Approach 2: Using Area of Triangle Formed by Points for Collinearity (Time: O(1), Space: O(1))
Three points are collinear when the triangle they form has zero area. Using the determinant formula for the area of a triangle with coordinates:
Area = x1(y2 - y3) + x2(y3 - y1) + x3(y1 - y2)
If the computed value equals zero, the points lie on a straight line and the boomerang is invalid. Any non‑zero value means the points form a triangle, which satisfies the boomerang condition. This technique is mathematically equivalent to the slope method but framed through geometric area.
The computation uses only a few arithmetic operations and no additional memory, giving the same O(1) time and O(1) space complexity. Some engineers prefer this approach because the determinant formula is widely used in computational geometry.
Recommended for interviews: The slope comparison using cross multiplication is typically expected. It directly expresses the definition of collinearity and avoids floating‑point division. The triangle area formula demonstrates deeper geometry intuition, but both solutions run in constant time. Showing either approach signals strong fundamentals with coordinate geometry and basic mathematical reasoning.
To determine if the three points form a boomerang, we first check if any two points are the same, which would immediately disqualify them as a boomerang since all points must be distinct. Then, we check that the slope between any two pairs of points is different, which ensures they are not collinear. If the slopes between (points[0], points[1]) and (points[0], points[2]) are different, the points are not on a straight line and hence form a boomerang.
This solution first checks if all points are distinct and ensures the slopes between the points are not equal to determine if the points are not collinear. The slopes are compared using cross multiplication to avoid division.
Time Complexity: O(1) because each operation takes constant time.
Space Complexity: O(1) since no additional space outside of input is used.
The area of a triangle can be used to determine collinearity of three points. If the area is zero, the points are collinear. The formula for the area of the triangle formed by points A(x1,y1), B(x2,y2), and C(x3,y3) is 0.5 * |x1(y2-y3) + x2(y3-y1) + x3(y1-y2)|. If the area derived from this formula is zero, the points are on a straight line. If the area is non-zero, the points form a triangle, suggesting a valid boomerang.
This implementation calculates the area using a cross-product-based approach. If the computed area is not zero, the points form a valid triangle.
Time Complexity: O(1) because each operation takes constant time.
Space Complexity: O(1) since no additional space outside of input is used.
Let the three points be (x_1, y_1), (x_2, y_2), and (x_3, y_3). The formula for calculating the slope between two points is \frac{y_2 - y_1}{x_2 - x_1}.
To ensure that the three points are not collinear, the condition \frac{y_2 - y_1}{x_2 - x_1} neq \frac{y_3 - y_2}{x_3 - x_2} must be satisfied. By transforming the equation, we get (y_2 - y_1) cdot (x_3 - x_2) neq (y_3 - y_2) cdot (x_2 - x_1).
Note:
x_1 = x_2, the transformed equation still holds.Time complexity is O(1).
| Approach | Complexity |
|---|---|
| Using Slope to Determine Collinearity | Time Complexity: O(1) because each operation takes constant time. |
| Using Area of Triangle Formed by Points for Collinearity | Time Complexity: O(1) because each operation takes constant time. |
| Slope Comparison | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Slope Comparison (Cross Multiplication) | O(1) | O(1) | General case; simplest implementation without floating point division |
| Triangle Area / Determinant Method | O(1) | O(1) | When applying computational geometry formulas or determinant logic |
1037. Valid Boomerang | Interview Preparation | Tamil | code io • code io - Tamil • 2,709 views views
Watch 9 more video solutions →Practice Valid Boomerang with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor