1037. Valid Boomerang

Problem Description

Given an array points, which contains three elements, where each element points[i] = [xi, yi] represents a coordinate on the X-Y plane, the task is to determine if these three points constitute a boomerang. A boomerang is defined as a set of three points that comply with two conditions: first, each point must be distinct from the others; and second, the points must not lie in a straight line — that is, they shouldn't all be collinear. The function should return true if the points form a boomerang, and false otherwise.

Intuition

To determine whether three points (p1, p2, and p3) form a boomerang, we need to ensure they are not collinear. A straightforward way to verify this is by checking if the slope between p1 and p2 is different from the slope between p2 and p3. If both slopes are equal, the points lie on a straight line, which disqualifies them from forming a boomerang.

Mathematically, the slope between two points (x1, y1) and (x2, y2) is given by (y2 - y1) / (x2 - x1). For points not to be collinear, the slopes (y2 - y1) / (x2 - x1) and (y3 - y2) / (x3 - x2) should be different. To avoid division by zero, we can cross-multiply and compare the products: (y2 - y1) * (x3 - x2) should not be equal to (y3 - y2) * (x2 - x1).

The solution code implements this concept by taking the three points from the points array and calculating the products of differences as described, returning true if they're not equal and false otherwise. By cross-multiplying, we avoid the complication of dealing with the exact slope values or the divisions, simplifying our implementation and ensuring it remains robust even when vertical lines are involved (where the slope would be undefined).

Learn more about Math patterns.

Solution Approach

The solution to this problem involves using the formula for the slope of a line and checking if the slope of the line between the first two points (x1, y1) and (x2, y2) is different from the slope of the line between the second two points (x2, y2) and (x3, y3).

To avoid the division operation and potential division by zero errors when calculating the slope, the implementation uses cross multiplication.

Here is the algorithm in a step-by-step fashion:

1. Extract the coordinates of the three points from the input list.
2. Compute the product of differences for the first and second points: (y2 - y1) * (x3 - x2).
3. Compute the product of differences for the second and third points: (y3 - y2) * (x2 - x1).
4. Compare the two computed products. If they are equal, it indicates that the slopes are the same and hence the points are collinear. If the products are not equal, the points are not collinear.
5. Return true if the products are not equal (not collinear), else return false.

The above steps are represented in the given solution code:

1class Solution:
2    def isBoomerang(self, points: List[List[int]]) -> bool:
3        (x1, y1), (x2, y2), (x3, y3) = points
4        return (y2 - y1) * (x3 - x2) != (y3 - y2) * (x2 - x1)

This code makes use of basic arithmetic operations and no additional data structures or complex patterns. It relies on the fact that if the product of the differences is equal for both pairs of points, then the three points lie on the same line (are collinear), which means they cannot form a boomerang. Otherwise, if the products are different, the points form a vertex of a non-straight line and hence do form a boomerang.

Example Walkthrough

Let's consider an example where we have three points p1, p2, and p3 given by their coordinates: p1 = [1, 1], p2 = [2, 3], and p3 = [3, 2]. We want to find out if these points form a boomerang.

Using the provided solution approach, we will take the following steps:

1. Extract the coordinates of the three points from the input list. We already have that as:

   • p1 (x1, y1) = (1, 1)
   • p2 (x2, y2) = (2, 3)
   • p3 (x3, y3) = (3, 2)

2. Compute the product of differences for the first and second points: (y2 - y1) * (x3 - x2), which will be:

   • (3 - 1) * (3 - 2) = 2 * 1 = 2

3. Compute the product of differences for the second and third points: (y3 - y2) * (x2 - x1), which will be:

   • (2 - 3) * (2 - 1) = -1 * 1 = -1

4. Compare the two computed products. In our example, 2 is not equal to -1, indicating that the slopes are different, and hence the points are not collinear.

5. Since the products are not equal, we return true, concluding that the points p1, p2, and p3 do indeed form a boomerang.

To summarize, the points (1, 1), (2, 3), and (3, 2) when plugged into our solution approach show that they are not collinear and hence form a boomerang. The function will return true in this case.

Solution Implementation

Time and Space Complexity

The time complexity of the given code is O(1) because the operations performed are constant and do not depend on the size of the input; the code always handles exactly three points.

The space complexity of the code is O(1) as well, since the space used does not scale with the input. The only additional space used is for the unpacked point coordinates, which is a constant amount of space for the three pairs of integers.

Learn more about how to find time and space complexity quickly using problem constraints.