algoadvance

Given an array points where points[i] = [xi, yi] represents a point on the X-Y plane, return true if these points form a boomerang, otherwise return false.

A boomerang is a set of three points that are all distinct and not in a straight line.

Example:

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

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

Clarifying Questions

  1. Can the points be negative? Yes, the points can have negative coordinates since they can be any on the X-Y plane.

  2. Is the input always valid in terms of having exactly three points? Yes, according to the problem statement, the function will always receive an array of exactly three points.

  3. Can the points be non-integer values? The problem statement does not specify otherwise, so we are assuming that all point coordinates are integers.

Strategy

To determine if the three points form a boomerang:

  1. Make sure that all the three points are distinct.
  2. Check if the points are not collinear (i.e., they do not lie on the same straight line).

To check if the points are collinear, we can use the concept of the slope. For points ((x1, y1)), ((x2, y2)), and ((x3, y3)), they are collinear if the slopes of the segments ((x1, y1)) to ((x2, y2)) and ((x1, y1)) to ((x3, y3)) are the same.

However, to avoid division (floating-point arithmetic), we can use the area of the triangle formed by the three points. If the area is zero, the points are collinear. This can be determined using the determinant: [ \text{Area} = \frac{1}{2} \left| x1(y2 - y3) + x2(y3 - y1) + x3(y1 - y2) \right| ] If this area is zero, the points are collinear.

Code

def isBoomerang(points):
    (x1, y1), (x2, y2), (x3, y3) = points

    # Check if all points are distinct
    if (x1 == x2 and y1 == y2) or (x1 == x3 and y1 == y3) or (x2 == x3 and y2 == y3):
        return False

    # Calculate the determinant of the matrix
    # | x1 y1 1 |
    # | x2 y2 1 |
    # | x3 y3 1 |
    # which is essentially the area check for collinearity discussed.
    # Formula: x1(y2 - y3) + x2(y3 - y1) + x3(y1 - y2).
    area = x1 * (y2 - y3) + x2 * (y3 - y1) + x3 * (y1 - y2)
    
    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

Time Complexity

This is because we are given exactly three points and we directly calculate the necessary values.

Try our interview co-pilot at AlgoAdvance.com