{x}
blog image

Valid Boomerang

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

Solution Explanation:

This problem checks if three given points form a boomerang. A boomerang is defined as three distinct points that are not collinear (i.e., they don't lie on the same straight line).

The solution leverages the concept of the slope of a line. Three points are collinear if the slope between any pair of points is the same. We can use the formula for the slope (m = (y2 - y1) / (x2 - x1)) to check for collinearity. However, to avoid division by zero, we can rearrange the slope equation to check if the cross product of two vectors formed by the points is zero.

The Core Idea:

Two vectors are defined by using the points as origins:

  • Vector 1: (x2 - x1, y2 - y1) from point 1 to point 2
  • Vector 2: (x3 - x2, y3 - y2) from point 2 to point 3

If these vectors are collinear, their cross product will be 0. The cross product of two 2D vectors (a, b) and (c, d) is given by (ad - bc). In our case:

Cross product = (y2 - y1)(x3 - x2) - (x2 - x1)(y3 - y2)

If the cross product is not equal to 0, the points are not collinear, forming a boomerang. The code efficiently computes this.

Time Complexity Analysis:

The solution performs a constant number of arithmetic operations regardless of the input size (since there are always only three points). Therefore, the time complexity is O(1).

Space Complexity Analysis:

The algorithm uses a constant amount of extra space to store variables. Therefore, the space complexity is O(1).

Code Explanation (Python Example):

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)

The Python code elegantly unpacks the points directly into variables (x1, y1, etc.). It then directly calculates the cross product and checks if it's non-zero, returning True if it is (a boomerang) and False otherwise. The formula is optimized to avoid division, preventing potential ZeroDivisionError exceptions. Other language versions follow the same logic, adapting syntax to their specific rules.

Example Usage:

[[1,1],[2,3],[3,2]] would return True because they don't form a straight line.

[[1,1],[2,2],[3,3]] would return False because they are collinear.

The solution's conciseness and efficiency make it optimal for solving the problem.