Valid Boomerang

Difficulty: Easy | Acceptance: 39.50% | Paid: No Topics: Array, Math, Geometry

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.

• Examples
• Constraints
• Approach 1: Slope Comparison
• Approach 2: Triangle Area
• Approach 3: Vector Cross Product

Examples

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

Approach 1: Slope Comparison

Intuition Three points are collinear if the slope between the first two points is equal to the slope between the last two points. To avoid division by zero (vertical lines), we compare the cross products of the differences.

Steps

• Extract coordinates for the three points.
• Calculate the slope difference using cross-multiplication: (y2 - y1) * (x3 - x2) vs (y3 - y2) * (x2 - x1).
• If they are not equal, the points are not collinear (and implicitly distinct if the math holds, though identical points result in 0=0 which correctly returns false).

from typing import List

class Solution:
    def isBoomerang(self, points: List[List[int]]) -> bool:
        x1, y1 = points[0]
        x2, y2 = points[1]
        x3, y3 = points[2]
        # Compare slopes (y2-y1)/(x2-x1) != (y3-y2)/(x3-x2)
        # Cross multiply to avoid division by zero
        return (y2 - y1) * (x3 - x2) != (y3 - y2) * (x2 - x1)

Complexity

• Time: O(1)
• Space: O(1)
• Notes: Constant time arithmetic operations.

Approach 2: Triangle Area

Intuition Three points form a triangle with a non-zero area if and only if they are not collinear. We can calculate the area using the determinant formula (shoelace formula).

Steps

• Extract coordinates.
• Calculate the area using the formula: 0.5 * |x1(y2 - y3) + x2(y3 - y1) + x3(y1 - y2)|.
• Return true if the area is not zero.

from typing import List

class Solution:
    def isBoomerang(self, points: List[List[int]]) -> bool:
        x1, y1 = points[0]
        x2, y2 = points[1]
        x3, y3 = points[2]
        # Calculate 2 * Area to avoid floating point numbers
        # Area = 0.5 * |x1(y2 - y3) + x2(y3 - y1) + x3(y1 - y2)|
        area = x1 * (y2 - y3) + x2 * (y3 - y1) + x3 * (y1 - y2)
        return area != 0

Complexity

• Time: O(1)
• Space: O(1)
• Notes: Using integer arithmetic (2*Area) avoids precision issues with floating point numbers.

Approach 3: Vector Cross Product

Intuition If we create two vectors from the three points (e.g., vector AB and vector AC), the points are collinear if the cross product of these two vectors is zero.

Steps

• Calculate vector 1: (x2 - x1, y2 - y1).
• Calculate vector 2: (x3 - x1, y3 - y1).
• Compute the cross product: v1.x * v2.y - v1.y * v2.x.
• Return true if the result is not zero.

from typing import List

class Solution:
    def isBoomerang(self, points: List[List[int]]) -> bool:
        x1, y1 = points[0]
        x2, y2 = points[1]
        x3, y3 = points[2]
        
        # Vector 1: (x2 - x1, y2 - y1)
        # Vector 2: (x3 - x1, y3 - y1)
        # Cross product: v1.x * v2.y - v1.y * v2.x
        return (x2 - x1) * (y3 - y1) != (y2 - y1) * (x3 - x1)

Complexity

• Time: O(1)
• Space: O(1)
• Notes: Geometrically intuitive approach using vector algebra.