Jobs

Interviews

Discussions

Valid Boomerang

Easy

Asked by:

8 views

Topics:

Arrays

Given an array points where points[i] = [x_i, y_i] 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 <= x_i, y_i <= 100

Try coding it in LeetCode

Valid Boomerang

Easy

Asked by:

8 views

Topics:

Arrays

Given an array points where points[i] = [x_i, y_i] 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 <= x_i, y_i <= 100

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

Are the input coordinates guaranteed to be integers, or could they be floating-point numbers?
What is the acceptable range for the coordinate values? Is there a maximum or minimum value?
Can any two or all three points be the same? If so, should that be considered a boomerang or not?
If the three points are collinear (lie on the same line), should that be considered a boomerang?
Are null or empty input arrays possible? If so, how should I handle them?

Brute Force Solution

Approach

A boomerang is formed by three points. To check if these three points form a valid boomerang, we can directly examine all the possible combinations of these points and verify whether they meet the required conditions. This approach involves comparing all possibilities to identify a valid boomerang.

Here's how the algorithm would work step-by-step:

Take the three points given to you.
If any two of these points are exactly the same location, then it's not a valid boomerang.
Next, imagine drawing a straight line between the first two points.
If the third point sits directly on that same line, then it is not a valid boomerang.
If neither of the above conditions are true, then the three points form a valid boomerang.

Code Implementation

def is_boomerang(points):
    point_a, point_b, point_c = points

    # If any two points are the same, it's not a boomerang.
    if point_a == point_b or point_a == point_c or point_b == point_c:
        return False

    # Check if the three points are on the same line.
    # This avoids division by zero when calculating slope
    if (point_b[1] - point_a[1]) * (point_c[0] - point_b[0]) == \
       (point_c[1] - point_b[1]) * (point_b[0] - point_a[0]):

        return False

    # If the points are distinct and not collinear, it's a boomerang.
    return True

Big(O) Analysis

Time Complexity

O(1) – The provided solution involves checking a fixed number of points (three), regardless of any external input size. The steps consist of pair-wise comparisons between these three points and a collinearity check, which take constant time. Therefore, the number of operations is constant and does not scale with any input, resulting in a time complexity of O(1).

Space Complexity

O(1) – The algorithm uses a fixed number of variables to store the coordinates of the three points and perform comparisons. No dynamic data structures like lists or hash maps are created. Therefore, the auxiliary space required remains constant regardless of the input size, resulting in O(1) space complexity.

Optimal Solution

Approach

The fastest way to determine if three points form a valid boomerang is to check if they all lie on the same line. This involves checking if the area formed by these points is zero, meaning they are collinear. If they are collinear, they do not form a boomerang.

Here's how the algorithm would work step-by-step:

Think about three points on a piece of paper. A boomerang needs to be formed by three different points.
If you connect all three points, a boomerang makes a little triangle (or a flat line, we'll get to that).
Calculate the area of the triangle made by these three points.
If the area is zero, it means the points all line up on a straight line, and it is not a boomerang.
Also make sure that all the points are actually different from each other; if you have two points in the exact same place, that's also not a boomerang.
If the area is anything other than zero, and all the points are different, it is a boomerang!

Code Implementation

def is_boomerang(points):
    point_one = points[0]
    point_two = points[1]
    point_three = points[2]

    # Need three distinct points to form a boomerang.
    if point_one == point_two or point_one == point_three or point_two == point_three:
        return False

    # Calculate the area of the triangle formed.
    area = (point_one[0] * (point_two[1] - point_three[1]) +
            point_two[0] * (point_three[1] - point_one[1]) +
            point_three[0] * (point_one[1] - point_two[1]))

    # A zero area indicates collinearity; not a boomerang.
    if area == 0:
        return False

    return True

Big(O) Analysis

Time Complexity

O(1) – The algorithm operates on a fixed number of points (three) regardless of the input size. Calculating the area of the triangle formed by these points involves a fixed number of arithmetic operations. Checking for duplicate points also takes a fixed amount of time. Therefore, the runtime is constant and does not scale with input size, resulting in O(1) time complexity.

Space Complexity

O(1) – The algorithm described only uses a few constant space variables to store and calculate the area of the triangle and compare points. No dynamic data structures such as lists or hash maps are used. Therefore, the amount of extra memory used does not depend on the input size (number of points), and the space complexity is constant.

Edge Cases

Case	How to Handle
Input is null or any of the point arrays is null	Throw an IllegalArgumentException or return false since null inputs are invalid.
Any two points are identical	Return false since a boomerang must have distinct points.
All three points are collinear (lie on the same line)	Return false because collinear points do not form a boomerang, which requires a non-zero area.
Points have extremely large or small coordinate values (potential integer overflow)	Use long data type for calculations to prevent integer overflow during area computation.
Points are very close together, leading to potential floating point precision issues	Accept a small tolerance for collinearity using a very small epsilon value during area calculation comparison to zero.
Input points array contains more or less than 3 elements	Throw an IllegalArgumentException or return false because the input is invalid.
One or more points has identical x and y coordinates (e.g. [0, 0], [0, 0], [1, 1])	The collinearity check will correctly handle such cases, returning false.
Points form a very thin, almost-collinear triangle	The area calculation, with a tolerance value, should still correctly determine if it's considered a valid boomerang.

Input is null or any of the point arrays is null

How to Handle:

Throw an IllegalArgumentException or return false since null inputs are invalid.

Any two points are identical

How to Handle:

Return false since a boomerang must have distinct points.

All three points are collinear (lie on the same line)

How to Handle:

Return false because collinear points do not form a boomerang, which requires a non-zero area.

Points have extremely large or small coordinate values (potential integer overflow)

How to Handle:

Use long data type for calculations to prevent integer overflow during area computation.

Points are very close together, leading to potential floating point precision issues

How to Handle:

Accept a small tolerance for collinearity using a very small epsilon value during area calculation comparison to zero.

Input points array contains more or less than 3 elements

How to Handle:

Throw an IllegalArgumentException or return false because the input is invalid.

One or more points has identical x and y coordinates (e.g. [0, 0], [0, 0], [1, 1])

How to Handle:

The collinearity check will correctly handle such cases, returning false.

Points form a very thin, almost-collinear triangle

How to Handle:

The area calculation, with a tolerance value, should still correctly determine if it's considered a valid boomerang.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

Are the input coordinates guaranteed to be integers, or could they be floating-point numbers?
What is the acceptable range for the coordinate values? Is there a maximum or minimum value?
Can any two or all three points be the same? If so, should that be considered a boomerang or not?
If the three points are collinear (lie on the same line), should that be considered a boomerang?
Are null or empty input arrays possible? If so, how should I handle them?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

Take the three points given to you.
If any two of these points are exactly the same location, then it's not a valid boomerang.
Next, imagine drawing a straight line between the first two points.
If the third point sits directly on that same line, then it is not a valid boomerang.
If neither of the above conditions are true, then the three points form a valid boomerang.

Code Implementation

def is_boomerang(points):
    point_a, point_b, point_c = points

    # If any two points are the same, it's not a boomerang.
    if point_a == point_b or point_a == point_c or point_b == point_c:
        return False

    # Check if the three points are on the same line.
    # This avoids division by zero when calculating slope
    if (point_b[1] - point_a[1]) * (point_c[0] - point_b[0]) == \
       (point_c[1] - point_b[1]) * (point_b[0] - point_a[0]):

        return False

    # If the points are distinct and not collinear, it's a boomerang.
    return True

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

Think about three points on a piece of paper. A boomerang needs to be formed by three different points.
If you connect all three points, a boomerang makes a little triangle (or a flat line, we'll get to that).
Calculate the area of the triangle made by these three points.
If the area is zero, it means the points all line up on a straight line, and it is not a boomerang.
Also make sure that all the points are actually different from each other; if you have two points in the exact same place, that's also not a boomerang.
If the area is anything other than zero, and all the points are different, it is a boomerang!

Code Implementation

def is_boomerang(points):
    point_one = points[0]
    point_two = points[1]
    point_three = points[2]

    # Need three distinct points to form a boomerang.
    if point_one == point_two or point_one == point_three or point_two == point_three:
        return False

    # Calculate the area of the triangle formed.
    area = (point_one[0] * (point_two[1] - point_three[1]) +
            point_two[0] * (point_three[1] - point_one[1]) +
            point_three[0] * (point_one[1] - point_two[1]))

    # A zero area indicates collinearity; not a boomerang.
    if area == 0:
        return False

    return True

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Input is null or any of the point arrays is null	Throw an IllegalArgumentException or return false since null inputs are invalid.
Any two points are identical	Return false since a boomerang must have distinct points.
All three points are collinear (lie on the same line)	Return false because collinear points do not form a boomerang, which requires a non-zero area.
Points have extremely large or small coordinate values (potential integer overflow)	Use long data type for calculations to prevent integer overflow during area computation.
Points are very close together, leading to potential floating point precision issues	Accept a small tolerance for collinearity using a very small epsilon value during area calculation comparison to zero.
Input points array contains more or less than 3 elements	Throw an IllegalArgumentException or return false because the input is invalid.
One or more points has identical x and y coordinates (e.g. [0, 0], [0, 0], [1, 1])	The collinearity check will correctly handle such cases, returning false.
Points form a very thin, almost-collinear triangle	The area calculation, with a tolerance value, should still correctly determine if it's considered a valid boomerang.

Input is null or any of the point arrays is null

How to Handle:

Throw an IllegalArgumentException or return false since null inputs are invalid.

Any two points are identical

How to Handle:

Return false since a boomerang must have distinct points.

All three points are collinear (lie on the same line)

How to Handle:

Return false because collinear points do not form a boomerang, which requires a non-zero area.

Points have extremely large or small coordinate values (potential integer overflow)

How to Handle:

Use long data type for calculations to prevent integer overflow during area computation.

Points are very close together, leading to potential floating point precision issues

How to Handle:

Accept a small tolerance for collinearity using a very small epsilon value during area calculation comparison to zero.

Input points array contains more or less than 3 elements

How to Handle:

Throw an IllegalArgumentException or return false because the input is invalid.

One or more points has identical x and y coordinates (e.g. [0, 0], [0, 0], [1, 1])

How to Handle:

The collinearity check will correctly handle such cases, returning false.

Points form a very thin, almost-collinear triangle

How to Handle:

The area calculation, with a tolerance value, should still correctly determine if it's considered a valid boomerang.