Problem Description

You are given an array points containing exactly three points on a 2D coordinate plane, where each point is represented as [x, y].

Your task is to determine if these three points form a boomerang.

A boomerang is defined as a set of three points that satisfy two conditions:

1. All three points must be distinct (no two points are the same)
2. The three points must not be in a straight line (they must not be collinear)

The solution checks whether the three points are collinear by comparing slopes. For three points (x1, y1), (x2, y2), and (x3, y3), if they lie on the same line, the slope from point 1 to point 2 would equal the slope from point 2 to point 3.

Instead of directly comparing slopes as (y2 - y1)/(x2 - x1) ≠ (y3 - y2)/(x3 - x2), the code uses cross-multiplication to avoid division by zero issues: (y2 - y1) * (x3 - x2) ≠ (y3 - y2) * (x2 - x1).

If this inequality holds true, the points form a boomerang shape (they are not collinear), and the function returns true. Otherwise, it returns false.

Intuition

To determine if three points form a boomerang, we need to verify they don't all lie on the same straight line. The key insight is that if three points are collinear (on the same line), they share the same slope between consecutive pairs.

Think of it this way: if you're walking from point A to point B, and then from point B to point C, and all three points are on the same line, you're maintaining the same direction throughout your journey. The "steepness" or slope of your path remains constant.

Mathematically, for points to be collinear, the slope from the first point to the second point must equal the slope from the second point to the third point. If these slopes are different, the points must form a triangle or "boomerang" shape.

The slope between two points (x1, y1) and (x2, y2) is calculated as (y2 - y1)/(x2 - x1). So we want to check if: (y2 - y1)/(x2 - x1) ≠ (y3 - y2)/(x3 - x2)

However, division can be problematic when x2 - x1 = 0 or x3 - x2 = 0 (vertical lines). To avoid division by zero and potential floating-point precision issues, we can cross-multiply the inequality:

(y2 - y1) * (x3 - x2) ≠ (y3 - y2) * (x2 - x1)

This transformation preserves the inequality relationship while eliminating the need for division. If this cross-product inequality is true, the slopes are different, meaning the points don't lie on the same line and therefore form a valid boomerang.

Learn more about Math patterns.

Solution Approach

The implementation uses a straightforward mathematical approach based on slope comparison through cross-multiplication.

Step-by-step implementation:

1. Extract the three points: We unpack the input array to get three points with their coordinates:

   (x1, y1), (x2, y2), (x3, y3) = points

2. Apply the cross-multiplication formula: Instead of comparing slopes directly, we use the transformed equation to avoid division:

   return (y2 - y1) * (x3 - x2) != (y3 - y2) * (x2 - x1)

Why this works:

• If the three points are collinear, the slopes between consecutive pairs of points are equal: (y2 - y1)/(x2 - x1) = (y3 - y2)/(x3 - x2)
• Cross-multiplying this equation gives us: (y2 - y1) * (x3 - x2) = (y3 - y2) * (x2 - x1)
• To check if points form a boomerang (are NOT collinear), we check if this equality does NOT hold

Handling edge cases:

The cross-multiplication approach elegantly handles special cases:

• Vertical lines: When x2 - x1 = 0 or x3 - x2 = 0, direct slope calculation would cause division by zero. The cross-multiplication avoids this issue entirely.
• Duplicate points: If any two points are the same, the formula will correctly identify them as collinear (not a boomerang).

Time and Space Complexity:

• Time Complexity: O(1) - We perform a constant number of arithmetic operations regardless of input
• Space Complexity: O(1) - We only use a fixed amount of extra space for storing the extracted coordinates

Example Walkthrough

Let's walk through the solution with a concrete example to see how it determines if three points form a boomerang.

Example 1: Points that form a boomerang

Input: points = [[1, 1], [2, 3], [3, 2]]

Step 1: Extract the coordinates

• Point 1: (x1, y1) = (1, 1)
• Point 2: (x2, y2) = (2, 3)
• Point 3: (x3, y3) = (3, 2)

Step 2: Calculate the left side of the inequality

• (y2 - y1) * (x3 - x2) = (3 - 1) * (3 - 2) = 2 * 1 = 2

Step 3: Calculate the right side of the inequality

• (y3 - y2) * (x2 - x1) = (2 - 3) * (2 - 1) = (-1) * 1 = -1

Step 4: Compare the results

• Is 2 ≠ -1? Yes!
• Since the values are different, the points are NOT collinear
• Therefore, they form a boomerang → Return true

Example 2: Points that are collinear (NOT a boomerang)

Input: points = [[1, 1], [2, 2], [3, 3]]

Step 1: Extract the coordinates

• Point 1: (x1, y1) = (1, 1)
• Point 2: (x2, y2) = (2, 2)
• Point 3: (x3, y3) = (3, 3)

Step 2: Calculate the left side

• (y2 - y1) * (x3 - x2) = (2 - 1) * (3 - 2) = 1 * 1 = 1

Step 3: Calculate the right side

• (y3 - y2) * (x2 - x1) = (3 - 2) * (2 - 1) = 1 * 1 = 1

Step 4: Compare the results

• Is 1 ≠ 1? No!
• Since the values are equal, the points ARE collinear (they lie on the line y = x)
• Therefore, they do NOT form a boomerang → Return false

The cross-multiplication technique elegantly avoids division while correctly identifying whether the three points have the same slope between them, determining if they form a valid boomerang shape.

Solution Implementation

Time and Space Complexity

Time Complexity: O(1)

The algorithm performs a fixed number of operations regardless of input size:

• Unpacking three coordinate pairs from the input list: O(1)
• Computing four arithmetic operations: (y2 - y1), (x3 - x2), (y3 - y2), (x2 - x1): O(1)
• Two multiplication operations: (y2 - y1) * (x3 - x2) and (y3 - y2) * (x2 - x1): O(1)
• One comparison operation: !=: O(1)

Since the input always contains exactly 3 points and all operations are constant time, the overall time complexity is O(1).

Space Complexity: O(1)

The algorithm uses a fixed amount of extra space:

• Six variables to store the unpacked coordinates: x1, y1, x2, y2, x3, y3: O(1)
• No additional data structures are created
• The space used does not scale with input size (which is always fixed at 3 points)

Therefore, the space complexity is O(1).

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Attempting Direct Slope Comparison with Division

A common mistake is trying to directly calculate and compare slopes using division:

# INCORRECT APPROACH - Will fail with division by zero
def isBoomerang(self, points: List[List[int]]) -> bool:
    (x1, y1), (x2, y2), (x3, y3) = points
    slope1 = (y2 - y1) / (x2 - x1)  # Fails when x2 == x1
    slope2 = (y3 - y2) / (x3 - x2)  # Fails when x3 == x2
    return slope1 != slope2

Why it fails: When points form a vertical line or have the same x-coordinate, the denominator becomes zero, causing a runtime error.

Solution: Always use cross-multiplication to avoid division entirely, as shown in the correct implementation.

2. Incorrect Cross-Multiplication Formula

Another pitfall is mixing up the terms when cross-multiplying, leading to incorrect results:

# INCORRECT - Wrong pairing of terms
return (y2 - y1) * (x2 - x1) != (y3 - y2) * (x3 - x2)
# or
return (y2 - y1) * (y3 - y2) != (x2 - x1) * (x3 - x2)

Why it fails: These formulas don't correctly represent the slope comparison after cross-multiplication.

Solution: Remember the correct cross-multiplication pattern:

• Original: (y2 - y1)/(x2 - x1) != (y3 - y2)/(x3 - x2)
• Cross-multiply diagonally: (y2 - y1) * (x3 - x2) != (y3 - y2) * (x2 - x1)

3. Using Floating-Point Division for Comparison

Some might try to handle division by zero with special checks and then use floating-point comparison:

# PROBLEMATIC APPROACH
def isBoomerang(self, points: List[List[int]]) -> bool:
    (x1, y1), (x2, y2), (x3, y3) = points
  
    if x2 - x1 == 0 and x3 - x2 == 0:
        return False  # All points on same vertical line
    elif x2 - x1 == 0:
        return True   # Only first segment is vertical
    elif x3 - x2 == 0:
        return True   # Only second segment is vertical
  
    slope1 = (y2 - y1) / (x2 - x1)
    slope2 = (y3 - y2) / (x3 - x2)
    return slope1 != slope2  # Floating-point comparison issues

Why it fails:

• Overly complex with multiple edge cases
• Floating-point arithmetic can introduce precision errors
• Direct equality/inequality comparison of floating-point numbers is unreliable

Solution: Stick with integer arithmetic using cross-multiplication, which avoids both division by zero and floating-point precision issues.

4. Not Considering All Collinear Cases

Some implementations might check only consecutive point pairs:

# INCOMPLETE APPROACH
def isBoomerang(self, points: List[List[int]]) -> bool:
    (x1, y1), (x2, y2), (x3, y3) = points
  
    # Only checks if first two points are different
    if x1 == x2 and y1 == y2:
        return False
  
    return (y2 - y1) * (x3 - x2) != (y3 - y2) * (x2 - x1)

Why it fails: This doesn't fully handle cases where points 2 and 3 are identical, or points 1 and 3 are identical.

Solution: The cross-multiplication formula naturally handles all duplicate point cases. When any two points are identical, the formula will evaluate to equality (making the inequality false), correctly identifying them as non-boomerang configurations.