Scale Engineer

Valid Boomerang

Easy
#0991Time: O(1), because the input size is fixed to 3 points. We perform a constant number of comparisons and arithmetic operations.Space: O(1), as we only use a few variables to store coordinates and slopes, regardless of the input values.
Patterns
MathGeometry
Data structures
Array

Prompt

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 == 3
  • points[i].length == 2
  • 0 <= xi, yi <= 100

Approaches

2 approaches with complexity analysis and trade-offs.

This approach directly translates the geometric definition of a boomerang. It first checks for the distinctness of the three points. Then, it determines if they are collinear by calculating and comparing the slopes of the lines formed by pairs of points. This method is intuitive but suffers from the practical complexities of floating-point arithmetic and the need to handle special cases like vertical lines (which have an infinite slope).

Algorithm

  1. Let the three points be p1 = (x1, y1), p2 = (x2, y2), and p3 = (x3, y3).
  2. First, explicitly check if any two points are identical. If p1=p2 or p1=p3 or p2=p3, they cannot form a boomerang, so return false.
  3. Handle the case of vertical lines to avoid division by zero. If x1, x2, and x3 are all equal, the points are on a vertical line and thus collinear. Return false.
  4. If only two points share an x-coordinate (e.g., x1 == x2 but x1 != x3), they cannot all be collinear, so return true.
  5. If no vertical lines are involved, calculate the slopes using floating-point division:
    • slope12 = (double)(y2 - y1) / (x2 - x1)
    • slope13 = (double)(y3 - y1) / (x3 - x1)
  6. Compare the slopes. If slope12 is not equal to slope13, the points are not collinear, so return true. Otherwise, return false.

Walkthrough

The core idea is to verify the two conditions for a boomerang separately: distinctness and non-collinearity.

  1. Distinctness Check: We start by comparing each pair of points. If any two points have the same coordinates, the first condition is violated, and we can immediately return false.
  2. Collinearity Check using Slopes: If the points are distinct, we check if they lie on a single straight line. The standard way to do this is by comparing slopes. The slope of the line between p1 and p2 must be different from the slope of the line between p1 and p3. A major issue here is that a vertical line has an undefined slope, leading to a division-by-zero error. Therefore, we must add special logic to handle cases where x1 == x2 or x1 == x3 before performing any division. This leads to a multi-branch conditional structure that, while correct, is cumbersome.
class Solution {    public boolean isBoomerang(int[][] points) {        int[] p1 = points[0];        int[] p2 = points[1];        int[] p3 = points[2];         // 1. Check for distinctness        if ((p1[0] == p2[0] && p1[1] == p2[1]) ||             (p1[0] == p3[0] && p1[1] == p3[1]) ||             (p2[0] == p3[0] && p2[1] == p3[1])) {            return false;        }         // 2. Check for collinearity using slopes        // Handle vertical line case for p1-p2        if (p1[0] == p2[0]) {            // If p1-p2 is a vertical line, for all 3 to be collinear,            // p1-p3 must also be a vertical line.            return p1[0] != p3[0];        }         // Handle vertical line case for p1-p3        if (p1[0] == p3[0]) {            // This case is symmetric to the one above. Since we already checked            // p1[0] == p2[0], we know they are different, so they can't be collinear.            return true;        }         // General case: calculate and compare slopes        double slope12 = (double)(p2[1] - p1[1]) / (p2[0] - p1[0]);        double slope13 = (double)(p3[1] - p1[1]) / (p3[0] - p1[0]);         return slope12 != slope13;    }}

Complexity

Time

O(1), because the input size is fixed to 3 points. We perform a constant number of comparisons and arithmetic operations.

Space

O(1), as we only use a few variables to store coordinates and slopes, regardless of the input values.

Trade-offs

Pros

  • The logic is a direct implementation of the slope formula, which can be easy to understand conceptually.

Cons

  • Requires complex conditional logic to handle vertical lines (division by zero).

  • The use of floating-point numbers for equality comparison is generally discouraged due to potential precision errors.

  • The code is more verbose and prone to implementation errors compared to the cross-product method.

Solutions

class Solution {public  boolean isBoomerang(int[][] points) {    int x1 = points[0][0], y1 = points[0][1];    int x2 = points[1][0], y2 = points[1][1];    int x3 = points[2][0], y3 = points[2][1];    return (y2 - y1) * (x3 - x2) != (y3 - y2) * (x2 - x1);  }}

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem