LeetCode 1037 - Valid Boomerang

LeetCode Problem 1037

Difficulty: 🟢 Easy
Topics: Array, Math, Geometry

Solution

Problem Understanding

This problem asks us to determine whether three given points in a 2D Cartesian plane form a valid boomerang. A boomerang is defined as a set of three points that are all distinct and not in a straight line. In other words, the points must not coincide and must not be collinear.

The input is always an array points of length exactly 3, where each element is a list [xi, yi] representing the coordinates of a point. The output is a boolean: true if the points form a boomerang and false otherwise. The constraints guarantee that each coordinate is an integer between 0 and 100, so there is no need to handle floating-point precision issues or extremely large numbers.

Edge cases to consider include points that are exactly the same (duplicates), points that lie on the same horizontal or vertical line, and points that lie on a diagonal line (collinear). The problem guarantees that the input always has exactly three points, which simplifies the solution.

Approaches

The brute-force approach would involve checking all pairs of points to see if any are duplicates and then checking all three points to see if they lie on a straight line. This can be done using the slope formula: two points (x1, y1) and (x2, y2) define a slope (y2 - y1) / (x2 - x1), and three points are collinear if the slopes between pairs are equal. While this approach works, it requires explicit slope calculations, which can involve division and potential division by zero.

The optimal approach avoids floating-point division by using a cross multiplication trick to check for collinearity. Three points (x1, y1), (x2, y2), (x3, y3) are collinear if (y2 - y1)*(x3 - x2) == (y3 - y2)*(x2 - x1). This works because it is derived from the slope equality condition without performing any division. We also simultaneously check that all points are distinct to ensure no duplicates exist. This solution is simple, efficient, and robust.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(1)	O(1)	Checks slopes and duplicates explicitly using division
Optimal	O(1)	O(1)	Uses cross multiplication to check collinearity and distinctness

Algorithm Walkthrough

1. Extract the coordinates of the three points into variables (x1, y1), (x2, y2), (x3, y3) for clarity.
2. Check if any two points are identical. If any two points are the same, return false immediately because a boomerang requires all points to be distinct.
3. Compute the differences dy1 = y2 - y1, dx1 = x2 - x1, dy2 = y3 - y2, and dx2 = x3 - x2.
4. Use the cross multiplication formula to check collinearity: dy1 * dx2 == dy2 * dx1. If this equality holds, the points lie on the same line, so return false.
5. If the points are distinct and not collinear, return true.

This works because the cross multiplication condition exactly captures whether the slope between the first two points equals the slope between the last two points. Ensuring distinct points guarantees that the boomerang is not degenerate.

Python Solution

from typing import List

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

        # Check for distinct points
        if (x1 == x2 and y1 == y2) or (x1 == x3 and y1 == y3) or (x2 == x3 and y2 == y3):
            return False

        # Check collinearity using cross multiplication
        return (y2 - y1) * (x3 - x2) != (y3 - y2) * (x2 - x1)

The implementation starts by unpacking the coordinates for readability. It first checks for duplicates, returning false if any exist. Then it applies the cross multiplication formula to determine collinearity. If the points are distinct and the cross multiplication test passes, it returns true.

Go Solution

func isBoomerang(points [][]int) bool {
    x1, y1 := points[0][0], points[0][1]
    x2, y2 := points[1][0], points[1][1]
    x3, y3 := points[2][0], points[2][1]

    // Check for distinct points
    if (x1 == x2 && y1 == y2) || (x1 == x3 && y1 == y3) || (x2 == x3 && y2 == y3) {
        return false
    }

    // Check collinearity using cross multiplication
    return (y2 - y1)*(x3 - x2) != (y3 - y2)*(x2 - x1)
}

The Go implementation is structurally similar to Python. It explicitly extracts coordinates into variables for clarity. It handles the same checks for distinct points and collinearity. There are no nil or overflow concerns given the constraints.

Worked Examples

Example 1

Input: [[1,1],[2,3],[3,2]]

1. Extract coordinates: (1,1), (2,3), (3,2).
2. Check distinctness: all points are distinct.
3. Compute differences: dy1 = 2, dx1 = 1, dy2 = -1, dx2 = 1.
4. Cross multiplication: 2 * 1 != -1 * 1 → 2 != -1, so not collinear.
5. Return true.

Example 2

Input: [[1,1],[2,2],[3,3]]

1. Extract coordinates: (1,1), (2,2), (3,3).
2. Check distinctness: all points are distinct.
3. Compute differences: dy1 = 1, dx1 = 1, dy2 = 1, dx2 = 1.
4. Cross multiplication: 1 * 1 == 1 * 1 → 1 == 1, so collinear.
5. Return false.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(1)	There are always exactly three points, so all operations are constant time.
Space	O(1)	Only a fixed number of variables are used for computation.

The algorithm is efficient because it does not scale with input size; the constraints limit the problem to three points. Memory usage is constant, as we only store differences and coordinates.

Test Cases

# Provided examples
assert Solution().isBoomerang([[1,1],[2,3],[3,2]]) == True  # Non-collinear
assert Solution().isBoomerang([[1,1],[2,2],[3,3]]) == False # Collinear

# Duplicate points
assert Solution().isBoomerang([[1,1],[1,1],[2,2]]) == False
assert Solution().isBoomerang([[0,0],[0,0],[0,0]]) == False

# Horizontal line
assert Solution().isBoomerang([[0,0],[1,0],[2,0]]) == False

# Vertical line
assert Solution().isBoomerang([[1,0],[1,1],[1,2]]) == False

# Non-collinear with max coordinates
assert Solution().isBoomerang([[0,0],[0,100],[100,0]]) == True

Test	Why
[[1,1],[2,3],[3,2]]	Basic non-collinear example
[[1,1],[2,2],[3,3]]	Basic collinear example
[[1,1],[1,1],[2,2]]	Tests duplicate detection
[[0,0],[0,0],[0,0]]	All points identical
[[0,0],[1,0],[2,0]]	Horizontal line collinearity
[[1,0],[1,1],[1,2]]	Vertical line collinearity
[[0,0],[0,100],[100,0]]	Non-collinear with extreme coordinates

Edge Cases

One edge case is when two points coincide, which violates the "all distinct" requirement. If the algorithm fails to check for duplicates first, the collinearity test may give a misleading result. Another edge case is when points lie on a perfectly horizontal or vertical line. Without cross multiplication, slope calculations could involve division by zero. The cross multiplication approach elegantly avoids this. Finally, an edge case involves points at extreme coordinates like [0,0] and [100,100], which could cause overflow in languages without arbitrary integers, but Python handles large integers automatically and Go can handle it safely within the given constraints. The solution correctly handles all these cases.