We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

Valid Boomerang

Number: 1115

Difficulty: Easy

Paid? No

Companies: Google

Problem Description

Given three points in the X-Y plane, determine if they form a boomerang. A boomerang is a set of three distinct points that are not all in a straight line.

Key Insights

Verify that all three points are distinct.
Determine if the points are collinear by calculating the area of the triangle they form.
Use cross multiplication (determinant method) to avoid division and potential divide-by-zero errors.
The area formula: area = x1*(y2 - y3) + x2*(y3 - y1) + x3*(y1 - y2). If the area equals zero, the points are collinear.

Space and Time Complexity

Time Complexity: O(1)
Space Complexity: O(1)

Solution

The solution involves two main checks:

Check for distinctness: Ensure that no two points are identical.
Check for collinearity: Calculate the area using the determinant formula. If the calculated area is zero, the points lie on a straight line, and the function returns false. Otherwise, they form a boomerang. Data Structures: Only variables are used to store the points and intermediate values. Algorithm: Simple arithmetic operations provide the result in constant time.

Code Solutions

# Define a function to determine if three points form a boomerang.
def isBoomerang(points):
    # Unpack the coordinates of the three points.
    (x1, y1), (x2, y2), (x3, y3) = points
    
    # Check if any two points are the same (points must be distinct).
    if (x1, y1) == (x2, y2) or (x1, y1) == (x3, y3) or (x2, y2) == (x3, y3):
        return False
    
    # Compute the area (times 2) of the triangle using the determinant method.
    area = x1 * (y2 - y3) + x2 * (y3 - y1) + x3 * (y1 - y2)
    
    # If the area equals 0, the points are collinear.
    return area != 0

# Example usage
print(isBoomerang([[1,1], [2,3], [3,2]]))  # Output: True
print(isBoomerang([[1,1], [2,2], [3,3]]))  # Output: False

← Back to All Questions