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 <= 100In #1037 Valid Boomerang, you are given three points in a 2D plane and must determine if they form a valid boomerang. A boomerang is defined as three distinct points that are not collinear. The key observation is that if all three points lie on the same straight line, they cannot form a boomerang.
A common approach is to check collinearity. This can be done by comparing the slopes between pairs of points or by using the area of a triangle (via the cross product). If the slopes between the points are equal, or if the computed triangle area is zero, the points lie on the same line.
Using integer arithmetic with the cross-product form helps avoid floating-point precision issues. Since the problem involves only three points and constant calculations, the algorithm runs in O(1) time with O(1) extra space.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Check collinearity using slope or cross product | O(1) | O(1) |
NeetCode
Use these hints if you're stuck. Try solving on your own first.
3 points form a boomerang if and only if the triangle formed from them has non-zero area.
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, geometry-based problems like Valid Boomerang sometimes appear in coding interviews, especially for entry-level or easy rounds. They test a candidate's ability to translate mathematical observations into simple and efficient code.
No special data structure is required for this problem. The coordinates are typically stored in a simple array or list of points, and basic arithmetic operations are used to determine whether the points are collinear.
The optimal approach is to check whether the three points are collinear. This can be done by comparing slopes or by using the cross-product formula to compute the area of the triangle formed by the points. If the area is zero, the points lie on a straight line and do not form a valid boomerang.
Using the cross product avoids floating-point precision issues that can occur when comparing slopes. It relies only on integer arithmetic, making the check more reliable and efficient for determining whether three points lie on the same line.