Valid Boomerang Problem

Problem

Given an array points where points[i] = [xi, yi] 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.

Examples

Example 1:

1
2
3
4

Input:
points = [[1,1],[2,3],[3,2]]
Output:
 true

Example 2:

1
2
3
4

Input:
points = [[1,1],[2,2],[3,3]]
Output:
 false

Solution

Method 1 – Area/Determinant Check

Intuition

Three points are collinear (in a straight line) if the area of the triangle they form is zero. For points (x1, y1), (x2, y2), (x3, y3), the area is zero if and only if:

(x2 - x1) * (y3 - y1) == (y2 - y1) * (x3 - x1)

If not, the points form a valid boomerang.

Approach

  1. Check if all three points are distinct.
  2. Use the area/determinant formula to check if the points are collinear.
  3. Return true if not collinear and all points are distinct.

Code

1
2
3
4
5
6
7
8
9

class Solution {
public:
    bool isBoomerang(vector<vector<int>>& p) {
        return (p[0][0] != p[1][0] || p[0][1] != p[1][1]) &&
               (p[0][0] != p[2][0] || p[0][1] != p[2][1]) &&
               (p[1][0] != p[2][0] || p[1][1] != p[2][1]) &&
               (p[1][0] - p[0][0]) * (p[2][1] - p[0][1]) != (p[1][1] - p[0][1]) * (p[2][0] - p[0][0]);
    }
};
1
2
3
4
5
6

func isBoomerang(p [][]int) bool {
    return (p[0][0] != p[1][0] || p[0][1] != p[1][1]) &&
           (p[0][0] != p[2][0] || p[0][1] != p[2][1]) &&
           (p[1][0] != p[2][0] || p[1][1] != p[2][1]) &&
           (p[1][0]-p[0][0])*(p[2][1]-p[0][1]) != (p[1][1]-p[0][1])*(p[2][0]-p[0][0])
}
1
2
3
4
5
6
7
8

class Solution {
    public boolean isBoomerang(int[][] p) {
        return (p[0][0] != p[1][0] || p[0][1] != p[1][1]) &&
               (p[0][0] != p[2][0] || p[0][1] != p[2][1]) &&
               (p[1][0] != p[2][0] || p[1][1] != p[2][1]) &&
               (p[1][0] - p[0][0]) * (p[2][1] - p[0][1]) != (p[1][1] - p[0][1]) * (p[2][0] - p[0][0]);
    }
}
1
2
3
4
5
6
7
8

class Solution {
    fun isBoomerang(p: Array<IntArray>): Boolean {
        return (p[0][0] != p[1][0] || p[0][1] != p[1][1]) &&
               (p[0][0] != p[2][0] || p[0][1] != p[2][1]) &&
               (p[1][0] != p[2][0] || p[1][1] != p[2][1]) &&
               (p[1][0] - p[0][0]) * (p[2][1] - p[0][1]) != (p[1][1] - p[0][1]) * (p[2][0] - p[0][0])
    }
}
1
2
3
4
5
6

class Solution:
    def isBoomerang(self, p: list[list[int]]) -> bool:
        return (p[0][0] != p[1][0] or p[0][1] != p[1][1]) and \
               (p[0][0] != p[2][0] or p[0][1] != p[2][1]) and \
               (p[1][0] != p[2][0] or p[1][1] != p[2][1]) and \
               (p[1][0] - p[0][0]) * (p[2][1] - p[0][1]) != (p[1][1] - p[0][1]) * (p[2][0] - p[0][0])
1
2
3
4
5
6
7
8

impl Solution {
    pub fn is_boomerang(p: Vec<Vec<i32>>) -> bool {
        (p[0][0] != p[1][0] || p[0][1] != p[1][1]) &&
        (p[0][0] != p[2][0] || p[0][1] != p[2][1]) &&
        (p[1][0] != p[2][0] || p[1][1] != p[2][1]) &&
        (p[1][0] - p[0][0]) * (p[2][1] - p[0][1]) != (p[1][1] - p[0][1]) * (p[2][0] - p[0][0])
    }
}
1
2
3
4
5
6
7
8

class Solution {
    isBoomerang(p: number[][]): boolean {
        return (p[0][0] !== p[1][0] || p[0][1] !== p[1][1]) &&
               (p[0][0] !== p[2][0] || p[0][1] !== p[2][1]) &&
               (p[1][0] !== p[2][0] || p[1][1] !== p[2][1]) &&
               (p[1][0] - p[0][0]) * (p[2][1] - p[0][1]) !== (p[1][1] - p[0][1]) * (p[2][0] - p[0][0]);
    }
}

Complexity

  • ⏰ Time complexity: O(1), only a constant number of operations.
  • 🧺 Space complexity: O(1), only a constant amount of extra space is used.