Domain 1EasyCORE

Valid Boomerang

The problem requires determining whether three given points on a 2D plane form a boomerang. A boomerang is defined as a set of three distinct points that are not collinear (i.e., they do not lie on the same straight line).

Domain: Easy•Updated: 2026-08-31
#Algorithms#LeetCode#qwen2.5-coder:14b#Math

1037. Valid Boomerang

Model: qwen2.5-coder:14b
Topics: Math
FAANG asked: 1
Acceptance rate: 37.7%


Problem Breakdown

The problem requires determining whether three given points on a 2D plane form a boomerang. A boomerang is defined as a set of three distinct points that are not collinear (i.e., they do not lie on the same straight line).

Inputs:

  • points: An array of three arrays, where each inner array contains two integers representing the x and y coordinates of a point.

Outputs:

  • A boolean value (true or false) indicating whether the points form a boomerang.

Implicit Constraints:

  • The input array will always contain exactly three points.
  • Each point is represented by an array of two integers, both within the range [0, 100].
  • Points must be distinct; duplicate points are not allowed.

Intuition

A brute-force approach would involve checking if any two points are identical and then verifying that the slope between each pair of points is different. However, this method can be inefficient and error-prone due to potential division by zero when calculating slopes.

The key insight is to use the concept of the area of a triangle formed by three points. If the area is non-zero, the points are not collinear and thus form a boomerang. The area can be calculated using the determinant method, which avoids issues with division and provides a straightforward way to check for collinearity.

Approach

  1. Input Validation: Ensure that all three points are distinct.
  2. Area Calculation: Use the determinant formula to calculate the area of the triangle formed by the three points: [ \text{Area} = \frac{1}{2} \left| x_1(y_2 - y_3) + x_2(y_3 - y_1) + x_3(y_1 - y_2) \right| ] If the area is non-zero, the points are not collinear and form a boomerang.
  3. Return Result: Return true if the area is non-zero; otherwise, return false.

Complexity Analysis

  • Time Complexity: (O(1)) - The algorithm involves a constant number of arithmetic operations regardless of input size.
  • Space Complexity: (O(1)) - No additional data structures are used that grow with input size.

Solution

class Solution:
    def isBoomerang(self, points: List[List[int]]) -> bool:
        # Extract coordinates for clarity
        x1, y1 = points[0]
        x2, y2 = points[1]
        x3, y3 = points[2]
        
        # Calculate the determinant (twice the area of the triangle)
        area = x1 * (y2 - y3) + x2 * (y3 - y1) + x3 * (y1 - y2)
        
        # If the area is non-zero, the points are not collinear
        return area != 0

Edge Cases Handled

  • Distinct Points: The solution inherently checks for distinct points by calculating the area. If any two points were identical, the area would be zero.
  • Zero Area (Collinear Points): The solution correctly identifies collinear points by checking if the calculated area is zero.
  • Boundary Values: The solution handles points with coordinates at the boundary values (0 and 100) without any issues, as it uses integer arithmetic.