# Valid Boomerang
**Difficulty:** EASY
[External](https://leetcode.com/problems/valid-boomerang)
Canonical: https://scaleengineer.com/dsa/problems/valid-boomerang
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math), [Geometry](https://scaleengineer.com/dsa/patterns/geometry)
**Data structures:** Array
---
## Problem
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
## Slope Comparison with Floating-Point Arithmetic
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).
**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.
**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.
### Explanation
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.

```java
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;
    }
}
```
### 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`.

## Geometric Approach using Cross-Product
A more robust and efficient approach uses a mathematical property of collinear points. Three points are collinear if and only if the area of the triangle they form is zero. This can be checked using a formula derived from the cross-product of two vectors formed by the points, which cleverly avoids floating-point arithmetic and division altogether. This method is superior as it handles all edge cases (including non-distinct points and vertical lines) with a single, simple expression.
**Time:** O(1), as it involves a fixed number of arithmetic operations. · **Space:** O(1), as no extra space proportional to the input is required.
**Pros:** Extremely concise and efficient, requiring only a single line of logic.; Avoids division and floating-point arithmetic, eliminating potential precision errors and division-by-zero exceptions.; Robustly handles all edge cases, including vertical lines and non-distinct points, without extra conditional checks.
**Cons:** The underlying mathematical connection (cross-product or area of a triangle) might be less immediately obvious than direct slope calculation.
### Explanation
This method relies on the geometric insight that three points `p1`, `p2`, `p3` are collinear if the vector `p1->p2` is parallel to the vector `p1->p3`. In 2D, two vectors `(dx1, dy1)` and `(dx2, dy2)` are parallel if their cross-product is zero, which is calculated as `dy1 * dx2 - dy2 * dx1 = 0`.

Let's define the vectors based on our points:
- Vector `v1` (from `p1` to `p2`): `(p2[0] - p1[0], p2[1] - p1[1])`
- Vector `v2` (from `p1` to `p3`): `(p3[0] - p1[0], p3[1] - p1[1])`

The points are collinear if `(p2[1] - p1[1]) * (p3[0] - p1[0]) == (p3[1] - p1[1]) * (p2[0] - p1[0])`.

A boomerang is formed if the points are **not** collinear, so we simply check for the inequality.

This single check also covers the distinctness requirement. If any two points are identical (e.g., `p1` and `p2`), then `p2[0] - p1[0]` and `p2[1] - p1[1]` will both be zero. This makes the left side of the equality `(p3[1] - p1[1]) * 0` and the right side `(p2[1] - p1[1]) * (p3[0] - p1[0])` which is `0 * ...`. The result is `0 == 0`, so the equality holds, our `!=` check fails, and the function correctly returns `false`.

```java
class Solution {
    public boolean isBoomerang(int[][] points) {
        int[] p1 = points[0];
        int[] p2 = points[1];
        int[] p3 = points[2];

        // The points are collinear if the cross-product of vectors p1->p2 and p1->p3 is zero.
        // (y2 - y1) * (x3 - x1) == (y3 - y1) * (x2 - x1)
        // A boomerang is formed if they are NOT collinear.
        // This single check handles both non-collinearity and distinctness.
        return (p2[1] - p1[1]) * (p3[0] - p1[0]) != (p3[1] - p1[1]) * (p2[0] - p1[0]);
    }
}
```
### Algorithm
1. Let the three points be `p1 = (x1, y1)`, `p2 = (x2, y2)`, and `p3 = (x3, y3)`.
2. Three points are collinear if the slope between `(p1, p2)` is equal to the slope between `(p1, p3)`.
   `slope(p1, p2) == slope(p1, p3)`
   `(y2 - y1) / (x2 - x1) == (y3 - y1) / (x3 - x1)`
3. To avoid division and floating-point issues, rearrange the equation using cross-multiplication:
   `(y2 - y1) * (x3 - x1) == (y3 - y1) * (x2 - x1)`
4. A boomerang requires the points to be non-collinear, so we check for the inequality:
   `(y2 - y1) * (x3 - x1) != (y3 - y1) * (x2 - x1)`
5. This single check is sufficient. It correctly identifies collinear points (returning `false`) and also implicitly handles cases where points are not distinct. If two points are the same, both sides of the equality become zero, correctly identifying them as 'collinear' for the purpose of this problem.

# Solutions
### Java

```java
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);
  }
}

```

### CPP

```cpp
class Solution {
public:
  bool isBoomerang(vector<vector<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);
  }
};

```

### Python

```python
class Solution:
    def isBoomerang(self, points: List[List[int]]) -> bool: (x1, y1), (x2, y2), (x3, y3) = points return (y2 - y1) * (x3 - x2) != (y3 - y2) * (x2 - x1)

```