Problem Description

The Valid Boomerang problem asks you to determine if three given points in a 2D plane form a "boomerang." A boomerang is defined as a set of three distinct points that are not all on a single straight line (i.e., they are non-collinear).

• The input is a list points with three elements, where each element is a list of two integers representing the x and y coordinates of a point: points = [[x1, y1], [x2, y2], [x3, y3]].
• Your task is to return True (or true) if the points form a valid boomerang, and False (or false) otherwise.
• Constraints:
  • Each point is a pair of integers.
  • All points must be distinct (no two points are the same).
  • There is only one set of three points in the input.

Thought Process

At first glance, it might seem that we need to check the distances between the points, or perhaps try to draw the triangle and see if it's "boomerang-shaped." However, the key insight is that the only requirement is that the three points are not in a straight line (not collinear).

If the points are collinear, they lie on the same straight line and thus do not form a boomerang. If they are not collinear, they form a triangle (which could be any shape, including a boomerang). So, the problem reduces to checking for collinearity.

The brute-force way would be to check for all possible slopes between pairs of points and see if they are the same, but this can lead to division by zero or floating-point inaccuracies. Instead, we can use the concept of the area of a triangle or the cross product to check for collinearity in a more robust way.

Solution Approach

• Step 1: Extract the coordinates
  Assign variables to the coordinates of the three points for clarity, e.g., (x1, y1), (x2, y2), (x3, y3).
• Step 2: Check for distinct points
  Ensure that all three points are distinct. If any two points are the same, return False immediately.
• Step 3: Check for collinearity using area or cross product
  The area of a triangle formed by three points is zero if and only if the points are collinear. The formula for the area is:
  Area = 0.5 * |x1(y2-y3) + x2(y3-y1) + x3(y1-y2)|
  Alternatively, the cross product of vectors AB and AC is zero if the points are collinear:
  (x2-x1)*(y3-y1) - (y2-y1)*(x3-x1) == 0
• Step 4: Return the result
  If the area (or cross product) is zero, return False (not a boomerang). Otherwise, return True.

This method avoids floating point errors and handles all edge cases.

Example Walkthrough

Let's walk through an example with the input points = [[1,1], [2,3], [3,2]].

• Assign: (x1, y1) = (1, 1), (x2, y2) = (2, 3), (x3, y3) = (3, 2)
• Check if all points are distinct: All are different, so continue.
• Compute the cross product:
  (x2-x1)*(y3-y1) - (y2-y1)*(x3-x1) = (2-1)*(2-1) - (3-1)*(3-1) = 1*1 - 2*2 = 1 - 4 = -3
• Since -3 ≠ 0, the points are not collinear. Return True.
• If the input was [[1,1], [2,2], [3,3]], the cross product would be zero, so the result would be False.

Code Implementation

class Solution:
    def isBoomerang(self, points):
        (x1, y1), (x2, y2), (x3, y3) = points
        # Check if all points are distinct
        if (x1, y1) == (x2, y2) or (x1, y1) == (x3, y3) or (x2, y2) == (x3, y3):
            return False
        # Check for collinearity using cross product
        return (x2 - x1) * (y3 - y1) != (y2 - y1) * (x3 - x1)
      

class Solution {
public:
    bool isBoomerang(vector<vector<int>>& points) {
        int x1 = points[0][0], y1 = points[0][1];
        int x2 = points[1][0], y2 = points[1][1];
        int x3 = points[2][0], y3 = points[2][1];
        // Check if all points are distinct
        if ((x1 == x2 && y1 == y2) || (x1 == x3 && y1 == y3) || (x2 == x3 && y2 == y3))
            return false;
        // Check for collinearity using cross product
        return (x2 - x1)*(y3 - y1) != (y2 - y1)*(x3 - x1);
    }
};
      

class Solution {
    public boolean isBoomerang(int[][] points) {
        int x1 = points[0][0], y1 = points[0][1];
        int x2 = points[1][0], y2 = points[1][1];
        int x3 = points[2][0], y3 = points[2][1];
        // Check if all points are distinct
        if ((x1 == x2 && y1 == y2) || (x1 == x3 && y1 == y3) || (x2 == x3 && y2 == y3))
            return false;
        // Check for collinearity using cross product
        return (x2 - x1) * (y3 - y1) != (y2 - y1) * (x3 - x1);
    }
}
      

var isBoomerang = function(points) {
    const [x1, y1] = points[0];
    const [x2, y2] = points[1];
    const [x3, y3] = points[2];
    // Check if all points are distinct
    if ((x1 === x2 && y1 === y2) || (x1 === x3 && y1 === y3) || (x2 === x3 && y2 === y3))
        return false;
    // Check for collinearity using cross product
    return (x2 - x1) * (y3 - y1) !== (y2 - y1) * (x3 - x1);
};
      

Time and Space Complexity

• Brute-force approach: If you checked all possible permutations or computed all slopes, it would still be O(1) because there are only three points.
• Optimized approach (cross product): The solution uses only a constant number of operations and variables, so the time complexity is O(1) and space complexity is also O(1).
• Why? The input size is fixed (three points), so regardless of the method, the work done does not depend on input size.

Summary

The Valid Boomerang problem is a classic collinearity check. By leveraging the cross product (or area) formula, we can determine if three points form a triangle (and thus a valid boomerang) in constant time and space. The key is to ensure all points are distinct and to avoid floating point errors by using integer arithmetic. This approach is both simple and robust, making the solution elegant and efficient.